We report on the changes in microstructure and phase composition in a high-Mn steel due to severe plastic deformation realized via high pressure torsion at different temperatures. Severe straining conducted at 20 °C and 300 °C allowed producing nanostructural states with a mean grain size less than 100 nm. Besides, straining at room temperature leaded to formation of strain-induced ε-martensite while at 300 °C fully austenite state was produced. Despite the revealed differences both states demonstrated similar, notably increased level of hardness up to ∼580 Hv.