Novel Ni-W-Co-Ta heavy alloys were cold rolled under room temperatures to characterize the microstructural evolution and mechanical properties by using optical microscopy, scanning electron microscopy, transmission electron microscopy, X-ray diffractometry, electron back scattered diffraction, tensile testing and microhardness testing. The results show that equiaxial grains were elongated along the rolling direction and a fibrous texture could be observed with an increase in deformation, in which a large number of slip bands were generated to coordinate the intensive plastic deformation. The sharp increase in dislocation density significantly promoted the dislocation interaction, which, in turn, refined the grain size down to 25.2 nm. After 90% severe plastic deformation, the tensile strength is increased to 1953 MPa. The yield strength is increased to 1806 MPa, the hardness is increased to 534 HV, and the elongation is sharply decreased by 9.1%. The fracture morphology changed from a typical ductile fracture to quasi-cleavage and ductile mixed fractures.