In this work, austenitic high-Mn steel that exhibits both high strength and plasticity at extremely low temperatures was designed and investigated, which demonstrates a yield strength of 1022 MPa, a tensile strength of 1532 MPa, and an elongation of 25% at 4.2 K, and enables potential operating in low-temperature structural materials. Compared to at room temperature, both the yield strength and the tensile strength of the high-Mn steel at low temperature increased, while the elongation at break decreased. A comparative study of its microstructural evolution was carried out using X-ray diffraction, transmission electron microscopy, and electron backscatter diffraction. The microstructure analysis revealed that the dislocations and nano-twinning control the strain-hardening behavior of the twinning-induced plasticity behavior of the Fe-24Mn-3.5Cr-0.4C steel.