The rotary bending fatigue tests were to investigate the effect of the combined shot peening for surface nanocrystallization (CSPN) on the fatigue limit of titanium (TC4). CSPN formed nano-crystallization in surface layer of TC4, and may reduce and reducing the surface damage of TC4 by high energy shot peening. In the case of equiaxed microstructure, 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 CSPN is increased by 34%. But in the case of lamellar microstructure, the fatigue limits of the specimens by either the surface treatment process both of the high energy shot peening and CSPN. The main reason of fatigue improvement change is due to that the effect of surface nanocrystallization and surface damage repairing by CSPN is changed between the different microstructure of TC4.