A combination of experiments and modeling are used to address the vibration durability of structures subjected to different random vibration environments. Presented in this work are a set of experimental data comparing the rate of change of the first natural frequency and the measured time to failure, of simple structural members under repetitive shock (RS) vibration, single-axis electrodynamic (ED) vibration and multi-axis ED vibration. It was found that multi-axis testing is more severe than single-axis testing at the same level. In addition the RS system low frequency amplitude is often too weak to efficiently propagate the crack. Smoothing of the input power spectral density (PSD) or poor line resolution was also shown to change the time to failure of a test. A poor correlation was shown between the PSD and the rate of natural frequency change (RFC) over a wide frequency shift. The change in natural frequency caused the initial PSD to be ineffective in determining the total time to failure. A predictive, analytic methodology to quantify the RFC was developed to predict the fatigue life of a structure experiencing random vibration excitation. This method allows the estimation of fatigue life using the frequency domain, where only the input power spectral density, damping factor and structural information are required. The methodology uses linear elastic fracture mechanics for fatigue crack propagation and accounts for the frequency shifting that occurs due to fatigue crack evolution. The analytic model has been shown to compare favorably to both finite element analysis (FEA) and experimental results, for mild-steel cantilever beams. Monte Carlo simulations have been conducted to assess the sensitivity of the model predictions to uncertainties in the input parameters. In addition a semi-empirical model was developed whereby the input PSD and damping factor are measured from life tests, and the resulting time to failure and the acceleration factors between different vibration environments can be determined. The improved modeling methodology developed by this work are of value not only to structural designers who wish to design for dynamic environments, but also to test engineers who wish to qualify products through accelerated life testing, and to vibration engineers who wish to compare the relative severity of different random vibration environments, in terms of their potential to cause fatigue damage accumulation.