Heterogeneous microstructure with nano-precipitate and bimodal grain size distribution was obtained in a FeCoCrNiMn high-entropy alloy (HEA) doped with 0.5 at.% C by a controlled thermo-mechanical treatment. The coarse M₂₃C₆ carbides tend to aggregate along the fine grain boundaries. Compared to the sample with homogenous microstructure, the heterostructure FeCoCrNiMn-0.5at.%C HEA has approximately the same average grain size of 4.8 μm. However, it shows bimodal grain size distribution and higher volume fraction of the fine grains (<3 μm), resulting in the increase of yield strength from 552 to 632 MPa. The sample with heterostructure presents different mechanical responses and deformed microstructures in different regions, accounting for significant strain localization and high density of the geometrically necessary dislocations during tensile deformation. These deformation characteristics are beneficial to the enhancement of strain hardening capacity, thereby promoting strength-ductility synergy.