Abstract: Based on the random fatigue analysis by a spectral method, a new approach is proposed to evaluate fatigue damage of uncertain structure under stationary Gaussian load, in which interval variables are introduced to describe uncertain parameters of structural systems. In this proposed method, uncertainty of structure is defined by interval parameter variables, and randomness of external loads is described by probabilistic models. Interval frequency response functions of structure and dynamic response of uncertain structure under stationary Gaussian load are explicitly expressed by the Rational Series Expansions and the Extra Unitary Intervals. Interval expected fatigue damage rates of uncertain structure are calculated by the prediction model of the Tovo-Benasciutti fatigue damage under random loads. The changes of fatigue damage in given parameter intervals are approximately expressed by adjusting extra unitary intervals of corresponding uncertain parameters. Finally, two numerical examples are studied to illustrate the accuracy and the efficiency of the proposed method compared with the vertex method.