A gradient nanostructured (GNS) surface layer was fabricated on a Z5CND16-4 martensitic stainless steel by means of surface mechanical rolling treatment (SMRT). The microstructure in the GNS surface layer was characterized by using SEM and TEM. The results showed that the mean grain size increases with depth, from about 25 nm at the topmost surface layer to the initial value in the matrix. The total thickness of the grain-refined layer is about 150 mm. The electrochemical corrosion property of the SMRT sample was compared with that of the as-received sample in a 3.5%NaCl aqueous solution. It is shown that the pitting corrosion potential increases from about 0.179 V in the as-received sample to about 0.313 V in the SMRT sample, and the self-corrosion potential also increases evidently. The formation of nanostructures, the increased structural homogeneity, and the introduction of compressive residual stresses in the GNS surface layer, as well as the decreased surface roughness, were discussed to promote the pitting corrosion resistance of the SMRT sample.