In this paper, the surface microstructure of the laser shocked TC4 titanium alloy is analyzed by EBSD and TEM, respectively. The microstructure evolution law and the nanocrystal formation mechanism are revealed. Laser shock peening does not change the microscopic material composition, but it can refine and homogenize the original grains, transform the small-angle grain boundaries to the large-angle ones, reduce the texture pole density, and make the grain orientation be more random. The surface layer microstructure consists of nanocrystals, dislocation cells, high-density dislocations, and original coarse grains, in which the thickness of the nanocrystal layer is about 710.4 nm, and the overall influence depth is less than 100 μm. The surface nanocrystals are formed through the complex dislocation movement, which conforms to the continuous dynamic recrystallization mechanism. The surface crystal distortion energy is the largest and the temperature rise effect is the most prominent, so the recrystallization process is the most fully carried out and the grain refinement is the highest.