Tensile and high cycle fatigue behaviors of high-Mn austenitic steels, including 25Mn, 25Mn0.2Al, 25Mn0.5Cu, 24Mn4Cr, 22Mn3Cr and 16Mn2Al specimens, were investigated at 298 and 110 K. Depending on the alloying elements, tensile ductility of high-Mn steels either increased or decreased with decreasing temperature from 298 to 110 K. Reasonable correlation between the tendency for martensitic tranformation, the critical twinning stress and the percent change in tensile elongation suggested that tensile deformation of high-Mn steels was strongly influenced by SFE determining TRIP and TWIP effects. Tensile strength was the most important parameter in determining the resistance to high cycle fatigue of high-Mn steels with an exceptional work hardening capability at room and cryogenic temperatures. The fatigue crack nucleation mechanism in high-Mn steels did not vary with decreasing tempertature, except Cr-added specimens with grain boundary cracking at 298 K and slip band cracking at 110 K. The EBSD (electron backscatter diffraction) analyses suggested that the deformation mechanism under fatigue loading was significantly different from tensile deformation which could be affected by TRIP and TWIP effects.