In this study, the fatigue strength of authentic stainless steel AISI304 subjected to shot peening (SP) and ultrasonic nanocrystal surface modification (UNSM) techniques was investigated. The fatigue specimens made of AISI304 steel were compered in four different conditions: unpeened, UNSM-treated, shot peened and SP + UNSM. The fatigue strength of the specimens was investigated using a rotary bending fatigue tester at different stress levels. Results showed that the fatigue life of AISI304 can be increased through SP at the same stress level, but it can be further increased by combining SP and UNSM technique. Interestingly, the UNSM-treated specimen exhibited the longest fatigue life in comparison with the SP and SP+UNSM ones. The fractrography of the specimens are observed by scanning electron microscopy (SEM) in order to shed light on the fracture and crack initiation mechanisms. High and deep compressive residual stress induced by UNSM treatment may be responsible for the longest fatigue life of the UNSM-treated specimen.