To meet the surface strengthening requirements of high-strength, high-toughness, medium-heavy Ni–W alloys for warheads, the NiW750 alloy was investigated. The alloy was prepared through vacuum melting, homogenization, forging, and solution treatment. A composite-strengthened surface layer, characterized by gradient nanostructures and high-density nanoprecipitates, was then constructed in the NiW750 alloy through a combined ultrasonic shot peening (USP) and aging treatment. The effects of different USP parameters (amplitude, time, shot quantity, and diameter) and the aging process on the alloy’s surface hardening behavior were investigated, and the microstructure evolution and hardening mechanisms were analyzed. The results indicate that USP introduced three types of crystal defects into the alloy’s surface layer: gradient dislocations, gradient nanograins, and gradient nanotwins, which collectively formed a gradient-hardening layer. This process approximately doubled the surface hardness compared to the solid-solution state, with the hardened layer exceeding 450 μm. Although the depth and hardness of the hardened layer could be regulated within a certain range by adjusting USP parameters, the strengthening effect exhibited a saturation limit. Following aging treatment, the gradient structure, composed of these three types of crystal defects, was retained in the surface layer, and the hardness continued to exhibit a gradient distribution from the surface inward. Hardness at different depths further improved by varying increments: the hardness of the outermost surface, the gradient-hardened layer, and the core increased by 166.39, 59.25, and 115.30 HV, respectively. During aging, the crystal defects introduced by USP promoted the nucleation of the Ni₄W phase, leading to the formation of finer and higher-density nano-dispersed precipitates. Concurrently, the density of these three types of crystal defects decreased during aging. The competition between aging-induced nanoprecipitation and the attenuation of these crystal defects determined the hardness increments at different depths.