A medium-Mn steel with nominal composition 0.20C–5Mn–0.2Si–0.2Al–bal.Fe (in wt pct) was hot rolled to plate and heat-treated at temperatures ranging from 550 °C to 650 °C and times ranging from 1 to 20 hours to obtain different γ-austenite fractions and stabilities, with the remainder of the microstructure being a combination of either α-ferrite or α-ferrite + θ-carbides. It was shown that when the steel was heat-treated to produce greater quantities of room temperature metastable γ-austenite, the γ-austenite was less stable as the austenite-stabilizing elements were dispersed among a greater fraction of material. Austenite stability, which is correlated with the Ms^α temperature, was calculated thermodynamically by measuring the local phase composition via Atom Probe Tomography. Quasi-static tension and Charpy V-notch (CVN) testing revealed that the austenite stability is directly correlated with CVN energy, where more stable austenite produces increased values of CVN toughness from room temperature down to – 80 °C. We observed that reduced CVN toughness at − 80 °C and − 40 °C in materials with low austenite stability was due to γ-austenite transformation during cooling prior to CVN testing. This work highlights that for materials with high strength and CVN toughness, it is critical to pursue heat treatments that balance both the concentration and stability of γ-austenite, instead of concentration alone. This work further demonstrates the importance of nano-scale composition in the γ-austenite and the utility of fine θ-carbide particles in producing steels with moderate strength and superior low temperature toughness.