Severely deformed surface layers have been created by ultrasonic attrition technique on four steel sheets to investigate their influence on fatigue behaviour. A low-carbon (0.05%) ferritic steel and a medium-carbon (0.47%) normalized ferritic-pearlitic steel were selected to study the effect of carbon content on fatigue properties of carbon steels. Two stainless steels, Type 316L and Type 301LN, were also tested to study the influence of stability of the austenitic structure. Microstructural features were characterized by hardness measurements, X-ray diffraction and optical and electron microscopy. Fatigue properties were determined in flexural bending in the range 104 to 107 cycles. Crack nucleation and propagation stages were followed. In the attrition treatment thin severely deformed surface layers were found to form. Highly increased hardness was measured in these layers, especially for stainless steels, where also strain-induced martensite was formed. Drastic improvement in fatigue resistance was observed for all steels due to the surface nanocrystallization treatment.