In order to enhance the fatigue limit of titanium (TC4), the combined shot peening were employed. Firstly, nano-crystallization in surface layer of TC4 were carried out by high-energy shot peening, and then the surface repair shot peening with small balls were introduced for repairing the surface damage by high-energy shot peening, and reducing the surface roughness, thus to enhance the quality of nanocrystalline surface layer of TC4. The fatigue tests were performed using the specimens treated by the combined shot peening. In addition, the influence factors of fatigue limit, the behavior of fatigue crack initiation and propagation etc. are discussed. The results showed that the fatigue limit of TC4 specimen treated by high-energy shot peening is increased by 13%, while the fatigue limit of TC4 specimen treated by the compound shot peening process is increased by 34% (165MPa). The main reason of fatigue improvement is considered to be that the combined shot peening process may effectively repair the surface damage, and also there is the certain relationship between the fatigue limit improvement and the surface roughness reducing.