Graded microstructures with different grain sizes and depths were produced on the surface layer of S45C steel by ultrasonic nanocrystal surface modification (UNSM). Plasma nitriding at 500°C for 8h and 48h was employed to process the UNSMed sample surface and investigate the surface properties. Compared with the un-UNSMed samples, the enhancement of the surface hardness, the effective nitrogen diffusivity, and the fatigue strength were obtained after UNSM treatment. For the UNSM68000 (68,000mm −2 ) sample, a nitrogen enrichment region of approximately 30μm (for nitriding 8h) and 80μm (for nitriding 48h) was observed in the surface zone. Little effect on the internal nitriding is found because the quick nitriding reaction of nitrogen with the nano-grain sized ferrite and the nitrides weaken the effective nitrogen diffusion within the sample materials. The fatigue limit of the UNSMed sample with nitriding for 8h improved approximately 78MPa (for 34,000mm −2 ) and 125MPa (for 68,000mm −2 ) compared with the un-UNSMed sample for the enhancement of nitrogen diffusion. However, a decrease of the fatigue limit of the UNSMed sample with nitriding for 48h was induced by the surface defects (small voids) that were produced by the prolonged nitriding. A prolonged nitriding phenomenon was observed for the nitriding of nano-grain sized surface structures, and this phenomenon promoted the formation of a thicker compound layer and induced nitrogen gas to form voids in the sample surface region.