In this study, the effects of Ultrasonic Nano-crystal Surface Modification (UNSM) on residual stresses, microstructure changes and mechanical properties of austenitic stainless steel 304 were investigated. The dynamic impacts induced by UNSM leads to surface nanocrystallization, martensite formation, and the generation of high magnitude of surface compressive residual stresses (−1400 MPa) and hardening. Highly dense deformation twins were generated in material subsurface to a depth of 100 µm. These deformation twins significantly improve material work-hardening capacity by acting both as dislocation blockers and dislocation emission sources. Furthermore, the gradually changing martensite volume fraction ensures strong interfacial strength between the ductile interior and the two nanocrystalline surface layers and thus prevents early necking. The microstructure with two strong surface layers and a compliant interior embedded with dense nanoscale deformation twins and dislocations leads to both high strength and high ductility. The work-hardened surface layers (3.5 times the original hardness) and high magnitude of compressive residual stresses lead to significant improvement in fatigue performance; the fatigue endurance limit was increased by 100 MPa. The results have demonstrated that UNSM is a powerful surface engineering technique that can improve component mechanical properties and performance.