Random vibrations induce damage in structures, especially when they are operating close to their natural frequencies. The stationarity of the input excitation is one of the fundamental assumptions required for frequency-domain fatigue-damage theory. However, for real applications, excitation is frequently non-stationary and the identification of this non-stationarity is not easy. This study researches run-tests to identify the index of non-stationarity. Further, using excitation signals with different rates of amplitude-modulated non-stationarity, the index of non-stationarity is experimentally and theoretically researched with regards to the fatigue life. The experimental research was performed on a flexible structure that was excited close to a natural frequency. The experimental fatigue life is compared to the theoretical fatigue life under the stationarity assumption. The analysis of the experimental results reveals a close relation between the identified non-stationarity in the excitation signal and the fatigue life of the structure. It was found that amplitude-modulated non-stationary excitation results in a significantly shorter fatigue life if compared to a similar level of stationary excitation.