The problem of estimating the fatigue damage in randomly vibrating structures with uncertain parameters is considered. The loadings are assumed to be stationary and Gaussian. The corresponding accumulated fatigue damage is described through the rain-flow cycle counting algorithm. For stationary and ergodic loads, the accumulated rain-flow fatigue damage can be estimated if the system and the load spectrum are known. However, these estimates would be erroneous if the structure properties and/or the spectrum parameters of the loading are significantly uncertain. Corrections to account for the parameter uncertainties is usually obtained using the Gauss error propagation formula, and is accurate for small parameter variations. An alternative approach based on Wiener chaos expansions is employed to estimate the rain-flow fatigue damage in linear/nonlinear structural systems with parameter uncertainties. The performance of the proposed approach is compared with the Gauss error propagation formula. The proposed method is illustrated through fatigue damage estimation of three simplified examples involving a moving vehicle on a rough road, Morison's force due to random sea waves and the blade of a wind turbine. © 2010 Elsevier Ltd. All rights reserved.