Severe plastic deformation (SPD) techniques such as laser shock peening (LSP) have been widely adopted to modify microstructure of materials. Understanding the plastic deformation mechanisms during SPD will enable the optimization of SPD process to obtain desired microstructures. Using LSP technique, we modified surface microstructure of AISI 420 martensitic stainless steel containing both martensitic lath and carbide, and investigated deformation mechanisms based on microstructural evolution. High-resolution transmission electron microscopy and X-ray diffraction results revealed that the laser shock wave induced severe deformation in the original sub-micron carbide, resulting in carbide fragmentation in AISI 420 martensitic stainless steel. These LSP-induced carbide fragments and original carbides promote nanocrystallization of martensitic laths, because the carbide/matrix interface acts as an effective dislocation nucleation sites and an obstacle to the dislocation movement. The LSP-generated martensitic lath nanocrystallization is rationalized by two simultaneous subdivision modes: the intersection between longitudinal and transverse sub-boundaries developed from dense dislocation walls and transverse sub-boundaries transformed from dislocation tangles. In addition, the carbide decomposition happened simultaneously with severe plastic deformation, which was reflected by the decreasing continuous Cr concentration and the increment of Fe concentration with increasing deformation degree in the deformed carbide. Finally, fine grain strengthening, precipitation strengthening and dislocation strengthening induced by LSP contribute to an increase in the strength and ductility of AISI 420 martensitic stainless steel.