The enormous magnitude of 2 billion tons of alloys produced per year demands a change in design philosophy to make materials environmentally, economically, and socially more sustainable. This disqualifies the use of critical elements that are rare or have questionable origin. Amongst the major alloy strengthening mechanisms, a high-dispersion of second-phase precipitates with sizes in the nanometre range is particularly effective for achieving ultra-high strength. Here, we propose an alternative segregation-based strategy for sustainable steels, free of critical elements, which are rendered ultrastrong by second-phase nano-precipitation. We increase the Mn-content in a supersaturated, metastable Fe-Mn solid solution to trigger compositional fluctuations and nano-segregation in the bulk. These fluctuations act as precursors for the nucleation of an unexpected α-Mn phase, which impedes dislocation motion, thus enabling precipitation strengthening. Our steel outperforms most common commercial alloys, yet it is free of critical elements, making it a new platform for sustainable alloy design.