Fatigue failure of a gas-nitrided 4140 steel under axial cyclic loading results from a competition between surface crack initiation in the nitrided case and internal “fish-eye” cracking inside the core material. When nitriding is deep enough, the internal mechanism prevails in smooth specimens and fatigue strength improvement as compared to base metal is about 20% at 10⁶ cycles. In the present study, three V-notched specimens (blunt, medium, and severe) are designed to be representative of the stress gradient: (i) in a small rotary bending specimen, (ii) at the root of a gear tooth, and (iii) at the root of a very sharp notch. The cracking mechanism depends on the notch severity. The nitrided blunt notch fails from a fish-eye nucleated at the case/core boundary, whereas the medium and sharp notches fail from surface cracks. The high-cycle fatigue strength improvement varies from 80% for the blunt notch and to more than 100% for the sharp notch. The notch fatigue behaviour of nitrided steel is discussed by comparing the evolutions of internal and surface fatigue strengths with relative stress gradient.