A recent innovation in steel metallurgy allows the formation of carbide-free bainite at temperatures below 300 °C, with plates of bainitic ferrite ≈100 nm wide separated by films of carbon-enriched retained austenite ≈50 nm wide, which are inexpensive to make and show an impressive combination of strength and toughness. Heating the material leads to the transformation of austenite to cementite and untempered martensite, rendering the steel weak and brittle. The current work uses thermodynamic modelling to design new alloys with increased resistance to thermal decomposition while retaining desirable mechanical properties. All three alloys studied were found to consist of nanostructured carbide-free bainite using electron microscopy and X-ray diffraction and exhibited improved thermal stability, compared to existing alloys.