We propose a novel Fe-based HEA with nanosized precipitates and a heterogeneous grain distribution, achieving a strength-ductility combination comparable to state-of-the-art Ni- or Co-based HEAs. The alloy benefits from both precipitation hardening and hetero-deformation-induced strengthening attributed to the heterogeneous grain distribution, resulting in excellent yield strength of 1433 MPa, tensile strength of 1599 MPa, and ductility of 22%. The microstructural evolution and its influence on mechanical properties are unraveled with respect to the observation of precipitate-dislocation interaction and hetero-deformation-induced stress (HDI stress) evaluation. This study suggests that the challenge of balancing properties and cost can be addressed through optimized compositional and microstructural design.