With the development of new steels and processing techniques, there have been corresponding advances in the fatigue performance of steels. Methods to increase fatigue performance are typically designed to produce gradients in surface properties and are based on heat treating operations, including enhanced carburizing and induction hardening, as well as surface mechanical deformation. In this paper selected examples based on recent work on deep rolling is used to illustrate the importance of the base steel properties on the final performance of surface modified materials. The degree of fatigue improvement by deep rolling, a process to mechanically deform fillet surfaces to improve fatigue resistance in cylindrical components, depends on the deformation response of the substrate to the rolling process. Recent results on the behavior of three medium carbon steel alloys deformed at temperatures up to 360 °C, are discussed. Deep rolling increased fatigue resistance, and the degree of improvement was higher when deep rolling was applied in the dynamic strain aging (DSA) temperature range rather than at room temperature. Observed variations in fatigue performance are interpreted based on fundamental deformation mechanisms and are used to present an overall perspective on approaches to increase the fatigue resistance of conventional and newly developed steels.