The microhardness $HV$ and structure–phase state of austenitic steel 12Cr18Ni10Ti are investigated after severe plastic deformation induced by ultrasonic impact treatment (UIT) carried out for various times and in various mediums (temperatures) such as the air, argon gas, and liquid nitrogen. As shown, the surface $HV$ evolution with time (with the strain extent accumulated in the surface layer) has a cyclic character (of alternate strengthening/softening) during the air-UIT process. It has the parabolic character during the argon-UIT process and the sigmoidal character at the cryogenic UIT (in liquid nitrogen). The main microstructural feature of the steel after the air-UIT and argon-UIT processes is the formation of the dislocation cell structures with a cell size of 200–700 nm that provides the $HV$ value of $\cong$ 4 GPa. The maximum values of the surface $HV$ of the steel 12Cr18Ni10Тi ($HV$ = 5–5.66 GPa) are obtained after the cryogenic UIT due to the formation of the maximum volume fraction of $\alpha$ʹ-martensite ($\cong$ 53%) as well as the nanosize grains of $\alpha$ʹ-martensite (24 nm) and austenite (45 nm) and the nanotwins (60–120 nm). This is due to the low value of stacking fault energy ($\cong$ 30 mJ/m$^{2}$) and the applied UIT conditions (high strain rate of $\cong$ 10$^{3}$ and cryogenic (77 K) temperatures), which determine the Zener–Hollomon parameter magnitude ln$Z$ = 26, whereas for the air-UIT and argon-UIT processes at room temperature, it is equal to 15 and 17, respectively.