A cumulative damage rule is proposed for fatigue of metals under variable stress-amplitude loading. The rule is nonlinear and takes into account the sequence of stress levels, i.e., high-to-low or low-to-high changes of stress amplitudes. To facilitate probabilistic estimates of safety of structural elements subjected to fatigue loading, a stochastic model of fatigue damage is developed. The mean value and the variance of the fatigue life of an element are determined in terms of the statistics of the material properties and of the load parameters.