The influence of low energy laser peening on fatigue lives of Ti-6Al-4V was investigated. Laser peening was carried out on Ti-6Al-4V samples. Laser peened samples were characterized by residual stress analysis, surface roughness measurements, X-ray diffraction, optical microscopy, nanoindentation hardness tests, scanning and transmission electron microscopy and fatigue testing. Laser peening resulted in the formation of nanocrystallites on the surface and near surface regions with associated increase in hardness and introduction of compressive residual stress. Owing to positive influence of nanostructured surface and compressive residual stress, fatigue lives of the laser peened samples were significantly increased compared to the unpeened samples.