Nanostructured bainitic steels exhibit high strength as well as a combination of substantial ductility, fracture toughness, and sub-critical fatigue crack growth life. Therefore, they may have potential application in the structures that experience rolling and/or sliding fatigue, such as shafts, mining equipment, bearings, and rails. However, as repeated sliding frequently results in sub-surface microstructural evolution that changes the tribological response with time, such applications call for high wear resistance that is not entirely dependent on the initial strength. In the current investigation, three nanostructured bainitic blocks with lath thicknesses of 45, 54, and 77 nm were produced via austempering at temperatures of 250, 300, and 350 °C, respectively, from steel with the following chemical composition: Fe-0.86C-1.45Si-1.8Mn-0.47Al-1.88Co-0.23Mo (wt%). Under reciprocating sliding motion using a 10 mm spherical tungsten carbide indenter and a 10 kN load, we examined friction and microstructural evolution and compared the results to the initial morphology of bainite. After several cycles of deformation, all specimens showed hardening. However, when tested under sliding fatigue for up to 500 cycles, the steel austempered at the lowest temperature displayed the highest sub-surface hardness and lowest friction coefficient as well as being the most resistant to wear. White etching layer (WEL) and severely deformed layer (SDL) were formed as a result of repeated sliding. While the SDL showed alignment of retained austenite and bainitic laths along the direction of maximum shear stress, the WEL had extremely fine microstructure. WEL and SDL predominated in the specimens austempered at the lowest temperature and the specimens austempered at the maximum temperature, respectively. After 500 sliding cycles under austempered conditions at 250 and 350 °C, atomic probe tomography (APT) was utilised to examine the distribution of carbon in the deformed layers just beneath the wear track. In any of the austempered specimens following wear, no discernible change in carbon has been found.