Based on the probability conservation principle, a joint probability density evolution equation of random parameters and fatigue damage is derived. Probability density evolution surface and cumulative probability isoline of fatigue damage in term of the evolution equation can be used to predict the probability distribution of fatigue damage and fatigue reliability with a given damage threshold. The numerical solution of fatigue reliability for a constant-amplitude test has a good agreement with the experimental result. For a variable-amplitude fatigue test, the computation results, which are calculated according to probability parameters of two constant-amplitude fatigue life tests and Miner's rule, are also in good agreement with the experimental results.