A high-strength Ni-W-Co-Ta medium-heavy alloy (MHA) was prepared through the melting–casting–forging followed by cryogenic rolling process. Detailed microstructure and mechanical property characterizations were conducted to unveil the influence of cyrorolling on Ni-W-Co-Ta MHA. The results revealed that initial equiaxial grains were elongated along the rolling direction firstly and then transformed to fibrous texture with increase in accumulated deformation, in which a large number of slip bands were generated to coordinate the intensive plastic deformation. A sharp increase in dislocation density significantly promoted the dislocation interactions, which, in turn, refined the grains down to nanometer scale. The strength and hardness increased significantly with the increase of the deformation, whereas the elongation decreased sharply. The fracture morphology changed from a typical ductile mode for the undeformed sample gradually to quasi-cleavage and ductile mixed mode for 90% deformed material.