This study aims to understand the effects of toughness and hardness on two-body wear of nanostructured carbide-free bainitic steels. For this purpose, three different steel grades were austempered at 250 °C to obtain carbide-free bainitic microstructures with different mechanical properties. The mechanical properties were determined in terms of fracture toughness and hardness. The wear tests were carried-out at three different loads with two different types of abrasive papers. The results show that a carbide-free bainitic steel with an optimum combination of hardness and fracture toughness exhibits the highest wear resistance. It has been seen that hardness is not the only parameter in determining the abrasive wear resistance and retained austenite has a beneficial effect on two-body abrasive wear.