High-entropy alloys (HEAs) have been extensively studied in recent years. However, yield strength of HEAs in which austenite is the dominating phase is usually low, far from satisfying the engineering demands. Improving performance-cost ratio of such alloys will help for their practical structural applications. Here we report a novel strategy to produce ultrastrong, tough, and low-cost HEAs, in which heavy nitrogen-doping (2.6 at.%) was applied to an inexpensive metastable FeMnCoCr HEA. Coupled with simple thermomechanical processing, we produced a multi-heterostructure, which consisted of fine α-martensite laths, deformed austenite with dense dislocations, recrystallized ultrafine grains and nano-nitride precipitates. Our novel FeMnCoCrN HEA exhibits a high yield strength of 1310 MPa which is ~5.2 times stronger than its base alloy without nitrogen doping. In particular, the highly dislocated body-centered cubic (bcc) martensite laths formed in the austenitic deformation matrix has an unexpected area fraction up to 24%. The hetero-deformation induced strengthening then reaches 750 MPa at the yield point, leading to a remarkable yield strength elevation of the material. Moreover, the high nitrogen content changes the dominant deformation mechanism from martensitic transformation to twinning, which contributes to a satisfactory uniform elongation of 16.5%, while the material is further strengthened by the dynamically refined microstructure. The high-nitrogen duplex alloy design strategy developed here provides a new paradigm for developing high-performance fcc HEAs.