Ti6Al4V alloy was treated by ultrasound-aided deep rolling (UADR) for surface mechanical strengthening. The microstructure evolution of the UADR treated specimen was characterized by scanning electron microscopy (SEM), hardness test, X-ray diffraction (XRD) and transmission electron microscopy (TEM). The results show that obvious grain refinement is found after UADR treatment and a nano-structured surface layer is formed with an average grain size less than 20 nm in the immediate surface. Grain boundaries at about 150 μm away from the surface become distinguishable. In this area, although grain boundary structure keeps unchanged, there is an increase of dislocation density in those grains. The effect of grain refinement on fatigue performance was also discussed