The enhancement of the fatigue strength is significant for the engineering applications of commercial pure titanium and its alloys. The paper investigated improvement of fatigue strength for commercial pure titanium by combined high-energy shot peening. Firstly, nano-crystallization in surface layer of pure titanium was carried out by high-energy shot peening, and then the shot peening with small diameter shots was introduced to degrade the surface roughness, enhancing the quality of the nano-grained surface. The fatigue limit of pure titanium by high-energy shot peening turns out to be increased by 34%, and the fatigue limit of pure titanium by compound high-energy shot peening turns out to be increased by 52.3%, according to the results. Effective factors such as surface states etc. to fatigue life, the fatigue crack initiation and propagation behaviors were also discussed in this paper.