Fatigue zones in a material can be identified using ultrasonic waves, as it has been shown that their propagation speed will reduce when travelling through such a zone. However, as fatigue damage is usually concentrated in a thin near-surface layer, through-thickness measurements result in very small changes of the average propagation speed across the full thickness, which are potentially difficult to reliably correlate to specific fatigue states. In this study, we have completed fatigue state assessments using Rayleigh waves, which travel on the surface of a material, to maximise those changes. We found that the use of Rayleigh waves amplifies the changes in speed, after propagation in the damaged region, by a factor of up to ten. The monotonic nature of the reduction in wave speed was verified against the theory using dislocation density measurements. Finally, a stiffness-reducing finite-element modelling technique, able to capture the effects of fatigue on the time of flight of longitudinal bulk and Rayleigh waves, was also derived and verified against the experimental measurements.