An on-line algorithm of fatigue damage evaluation was proposed by modifying Wang–Brown’s method under multiaxial random loading. Wang–Brown’s method requires rearrangement for the strain history before the counting process starts, which is not suitable for on-line fatigue damage evaluation. So an algorithm based on simple range counting for equivalent relative strain was presented first, and then an on-line algorithm was proposed by defining the fatigue damage in each reversal as rain-flow counting parameter. The proposed on-line algorithm does not require any rearrangement for the strain history and the fatigue damage can be evaluated on-line.