The gradient nanostructure is machined on the aluminum (Al) alloy by the two-dimensional ultrasonic surface burnishing process (2D-USBP). The mechanism of why the gradient nanostructure enhances wear resistance is investigated. The mechanical properties and microstructure characterization for the gradient nanostructure are performed by operating a nanoindenter, transmission electron microscopy (TEM), and electron backscattered diffraction (EBSD). Dry wear tests are performed on the samples before and after machining to evaluate the wear resistance and mechanisms. The effect of the gradient nanostructure on the wear resistance is explored by developing the crystal plasticity (CP) finite element and molecular dynamics (MD) models. The characterization results show that the 2D-USBP sample prepared a gradient structure of ∼600 µm thick on the aluminum surface, increasing the surface hardness from 1.13 to 1.71 GPa and reducing the elastic modulus from 78.84 to 70.14 GPa. The optimization of the surface microstructure and the increase of the mechanical properties effectively enhance the wear resistance of the sample, with 41.20%, 39.07%, and 54.58% of the wear scar areas for the 2D-USBP treated samples to the original samples under 5, 10, and 15 N loads, respectively. The gradient nanostructure hinders the slip of dislocations inside the sample during the wear process and reduces the size and scope of plastic deformation; meanwhile, the resistance to deformation, adhesion, and crack initiation and propagation of the sample surface is improved, resulting in enhanced wear resistance.