This talk reviews the existing methods for predicting random fatigue of structures with Gaussian stress response, and presents a recently developed frequency domain method for fatigue prediction of structures with non-Gaussian stress response. Effect of parameter uncertainties on the fatigue life is studies. The method for predicting the fatigue life of non-Gaussian stress is based on a probability density function of the rain flow cycles obtained by a nonlinear, multi-stage regression approach. The probability density function of the rain flow cycles is a function of a few common statistical and frequency domain response parameters of the non-Gaussian stress including the mean, standard deviation, skewness, kurtosis, and spectral moments up to fourth order. The sensitivity of the probability function with respect to the regression parameters is examined. We have found that the proposed method is quite accurate when compared with Monte Carlo simulations.