Individual and synergy effects of shot peening (SP) and ultrasonic nanocrystal surface modification (UNSM) on rotary bending fatigue (RBF) behavior of AISI 4340 steel were systematically investigated at various bending stress levels in the range of 275-600 MPa. The results revealed that the fatigue behavior of the as-received sample was enhanced by SP and it was further enhanced by SP and UNSM combination, while the UNSM-treated one exhibited the highest enhancement in fatigue behavior. The fatigue behavior of the SP + UNSM sample was enhanced after SP, but it was found to be detrimental after UNSM. Apart from RBF experiments, individual and synergy effects of SP and UNSM on surface roughness, hardness, residual stresses and grain size were analyzed as well. Fractography of the samples was characterized by scanning electron microscope (SEM) and fatigue mechanisms of each sample were discussed based on the obtained observations. The finest grain size and highest compressive residual stress (CRS) obtained by UNSM in comparison with those of the SP and SP + UNSM was responsible for the best fatigue performance.