The formation mechanism and wear behavior of a gradient nanostructured (GNS) Inconel 625 alloy were investigated using SEM, TEM and ball-on-disc sliding wear tester. The results show that surface mechanical grinding treatment (SMGT) induced an approximately 800 μm-deep gradient microstructure, consisting of surface nano-grained, nano-laminated, nano-twined, and severely deformed layers, which resulted in a reduced gradient in micro-hardness from 6.95 GPa (topmost surface) to 2.77 GPa (coarse-grained matrix). The nano-grained layer resulted from the formation of high-density nano-twins and subsequent interaction between nano-twins and dislocations. The width and depth of the wear scar, wear loss volume, and wear rate of the SMGT-treated sample were smaller than those of untreated coarse-grained sample. Moreover, the wear mechanisms for both samples were mainly abrasive wear and adhesive wear, accompanied with mild oxidation wear. The notable wear resistance enhancement of the GNS Inconel 625 alloy was attributed to the high micro-hardness, high residual compressive stress, and high strain capacity of the GNS surface layer.