Laser shock peening of titanium alloys has been widely applied in the aerospace industry. However, little is known of the nanocrystalline formation characteristics and mechanisms. In this investigation, a nanocrystalline layer was formed in the duplex Ti-6Al-4V titanium alloy surface region by means of multiple pulsed laser shock peening (LSP). The phase transition and residual stress characteristics of LSP samples were analyzed with X-ray diffraction (XRD) and scanning electron microscopy (SEM). Transmission electron microscopy (TEM) was used to characterize the microstructure and morphologies. As the number of laser pulses increased for each location, higher grain refinement was observed. Micro-hardness testing showed that hardness increased with the number of pulses delivered to each location due to the formation of nanocrystalline layers and high dislocation density in the samples, and a gradient variation of the micro-hardness was obtained. In addition, mechanical twins and different dislocation configurations were formed in the α phase region while only dense dislocation tangles were observed in the β phase region after multiple laser pulse impacts.