Automotive industry has focused on the development of steels with high strength and toughness, which can meet both fuel economy and safety goal. Here, a new class of ultrafine-grained high-Mn steels containing nano-scale oxides has been developed using a powder metallurgy route. First, high-energy mechanical milling was processed to dissolve alloying elements in Fe as well as to reduce grain size to nanometer regime. Second, the ball-milled powder was consolidated using spark plasma sintering. During spark plasma sintering, nano-scale manganese oxides were generated in Fe-15Mn steels while nano-scale aluminum oxides were produced in Fe-15Mn-3Al-3Si steels. Finally, mechanical behaviors of coarse-grained Fe, ultrafine-grained Fe and ultrafine-grained high-Mn steels containing nano-scale oxides were compared. As a result, ultrafine-grained high-Mn steels containing nano-scale oxides exhibited superior strength without significant loss of toughness, owing to combined effects of grain refinement, twinning-induced plasticity (TWIP), and dispersion of nano-scale oxides.