Growing attention has been placed on high-entropy alloys (HEAs) owing to their promising mechanical properties. Particularly, HEAs in which the main crystal structure is fcc are attracting significant attention. Although such alloys exhibit a good combination of strength and ductility, they cannot meet the increasing demands of applications because of limited yield strengths. In recent years, researchers have tried to improve yield strengths of HEAs by refining grains and introducing interstitial atoms. However, the processing cost is high and is often accompanied by the significant loss of ductility. In this study, we propose a simple processing route incorporating cold rolling at medium thickness reductions and short-time annealing at medium temperatures to obtain a heterogeneous structure in Fe-Mn based HEAs consisting of deformed grains with an average diameter of several tens of microns and recrystallized ultrafine grains. By simultaneously introducing multiple strengthening mechanisms, including the strengthening contributed by the microstructural characteristics of dense dislocations, grain refinement, precipitates, ε-martensite, α-martensite, and recovery twins, as well as the strengthening induced by deformation twinning and ε-martensite phase transition that occurs continuously during deformation, the yield strength of the alloy significantly increases compared with that of the fully recrystallized material and reaches 825 MPa. Simultaneously, due to the activation of significant deformation twinning and deformation-induced martensitic transformation, the uniform elongation of the alloy is about 28.6%. The proposed material fabrication method is simple, cost-effective, and can effectively improve the mechanical properties of Fe-Mn based HEAs, providing new insight into optimizing the mechanical properties of low stacking fault energy alloys of the fcc structure.