Single-phase face-centered cubic (fcc) medium-entropy alloys (MEAs) generally exhibit good ductility but insufficient room temperature strength that limits their potential application. Here, a deformation mechanism of twin-induced transformation was achieved to strength the CoCrNi-base alloy with gradient nanostructure obtained by surface mechanical rolling treatment (SMRT) technique. Significantly, the SMRT processed CoCrNi-based alloy exhibits a substantial improvement in the mechanical property comparing with the wrought counterpart by increasing the yield strength from 964 to 1664 MPa and the ultimate tensile strength from 1210 to 1883 MPa, while maintaining a uniform elongation of 11.3%. The enhanced combination of strength and ductility attributes to the extra hardening from the synergistic effect of nanostructure and phase transformation.