The effects of gradient nanostructures induced by supersonic fine particle bombardment (SFPB) on the surface integrity, microstructural evolution, and mechanical properties of a Ni-W-Co-Ta medium-heavy alloy (MHA) were systematically investigated. The results show that gradient nanostructures are formed on the surface of Ni-W-Co-Ta MHA after SFPB treatment. At a gas pressure of 1.0 MPa and an impact time of 60 s, the ultimate tensile strength and yield strength of the alloy reached the maximum values of 1236 MPa and 758 MPa, respectively, which are 22.5% and 38.8% higher than those of the solid solution treated alloy, and the elongation (46.3%) is close to that of the solid solution treated alloy, achieving the optimal strength–ductility synergy. However, microcracks appear on the surface with excessive gas pressure and impact time, generating the relaxed residual stress and decreased strength. With the increase of the impact time and gas pressure, the depth of the deformation layer and the surface microhardness gradually increase, reaching the maximum values (29 μm and HV 451) at 1.0 MPa and 120 s. The surface grain size is refined to a minimum of 11.67 nm. Notably, SFPB treatment has no obvious effect on elongation, and the fracture mode changes from the ductile fracture before treatment to ductile–brittle mixed fracture after treatment.