The nanocrystalline surface was produced on 3Cr13 martensite stainless steel surface using high-current pulsed electron beam (HCPEB) technique. The structures of the nanocrystallized surface were characterized by X-ray diffraction and electron microscopy. Two nanostructures consisting of fine austenite grains (50–150 nm) and very fine carbides precipitates are formed in melted surface layer after multiple bombardments via dissolution of carbides and crater eruption. It is demonstrated that the dissolution of the carbides and the formation of the supersaturated Fe (C) solid solution play a determining role on the microstructure evolution. Additionally, the formation of fine austenite structure is closely related to the thermal stresses induced by the HCPEB irradiation. The effects of both high carbon content and high value of stresses increase the stability of the austenite, which leads to the complete suppression of martensitic transformation.