In order to clarify the effects of the hybrid surface modification process; a combination of Fine Particle Bombardment (FPB) treatment and nitriding, on the fatigue properties of AISI 4135 steel (stress concentration factor: α=2.36), high cycle fatigue tests were carried out with a rotational bending machine at room temperature. Observations of fracture surfaces and measurements of hardness and residual stress distributions were carried out to investigate the fracture mechanism and fatigue strength. It was revealed that treating process sequence did affect residual stress distributions. Compressive residual stress generated at the surface of FPB treated specimen after nitriding was higher than that of the one FPB treated before nitriding. It was clarified that the higher the specimen hardness was, the higher compressive residual stress was generated at the surface. Therefore, FPB treatment after nitriding increased the fatigue strength of steel.