Micro-structural evolution and grain refinement in ANSI 304 stainless steel subjected to multiple laser shock processing (LSP) impacts were investigated by means of cross-sectional optical microscopy and transmission electron microscopy observations. The plastic strain-induced grain refinement mechanism of the face-centered cubic (fcc) materials with very low stacking fault energy was identified. The micro-structure was obviously refined due to the ultra-high plastic strain induced by multiple LSP impacts. The minimum grain size in the top surface was about 50–200 nm. Multidirectional mechanical twin matrix (MT)–MT intersections led to grain subdivision at the top surface during multiple LSP impacts. Furthermore, a novel structure with submicron triangular blocks was found at the top surface subjected to three LSP impacts. The grain refinement process along the depth direction after multiple LSP impacts can be described as follows: (i) formation of planar dislocation arrays (PDAs) and stacking faults along multiple directions due to the pile up of dislocation lines; (ii) formation of submicron triangular blocks (or irregularly shaped blocks) by the intersection of MT–MT (or MT–PDA or PDA–PDA) along multiple directions; (iii) transformation of MTs into subgrain boundaries; (iv) evolution by continuous dynamic recrystallization of subgrain boundaries to refined grain boundaries. The experimental results and analyses indicate that a high strain with an ultra-high strain rate play a crucial role in the grain refinement process of fcc materials subjected to multiple LSP impacts.