Two important and desirable properties of materials for most structural applications are high tensile strength and ductility, which typically require high work hardening to delay necking. Here, we designed and tensile tested a face-centered cubic (fcc) Fe-Cr-Co-Ni medium-entropy alloy in which multiple deformation mechanisms are triggered during tensile loading at different temperatures to induce sustained work hardening. Our strategy involved control of the relative stabilities of the fcc, hcp (hexagonal close-packed), and bcc (body-centered cubic) phases in this quaternary system via high-throughput thermodynamic calculations. This alloy not only exhibits extensive deformation-induced nanotwinning at room temperature, but also displays a two-step sequential phase transformation [γ (fcc) → ε (hcp) martensite → α’ (bcc) martensite] at 77 K, which contrasts with the single-step phase transformation [γ → ε martensite] observed in many other fcc high/medium entropy alloys with a low stacking fault energy. The sequence of phase transformation at 77K was supported by first-principles density functional theory calculations. This work provides new templates for the design of alloys capable of multiple deformation mechanisms for sustained work hardening.