Abstract: The outstanding mechanical properties of medium-Mn steels (MMnS) are largely governed by the transformation-induced plasticity (TRIP) effect of retained austenite. However, obtaining a high fraction of mechanically stable retained austenite often requires high Mn contents and/or long intercritical annealing periods, thereby limiting the widespread application of MMnS. In this work, a multi-phase heterostructure dominated by ultrafine-grained multi-phase (UFG MP) zones and non-recrystallized (NRX) zones was developed in a MMnS (3 wt.% Mn) via short-term pre-annealing at 655 °C for 5 min, followed by intercritical annealing at 690 °C for 10 min. The formation of this heterostructure is mainly attributed to the precipitation of Mn-enriched nanosized cementite during pre-annealing. During subsequent intercritical annealing, these finely dispersed Mn-enriched cementite promote the nucleation of numerous ultrafine reversed austenite grains, thereby increasing the retained austenite fraction (from 6.9% to 10.3%) and facilitating the formation of UFG MP zones. Meanwhile, pronounced Zener pinning introduced by nanosized undissolved cementite promotes the formation of NRX zones in Mn-poor regions. Tensile tests demonstrate that the pre-annealed 3Mn steel achieves a substantially higher tensile strength than its non-pre-annealed counterpart, increasing from 565 to 715 MPa, while maintaining a similar uniform elongation (24.8% vs. 24.1%). The enhanced tensile properties are primarily attributed to the strong hetero-deformation-induced (HDI) hardening associated with the heterogeneous microstructure, together with the enhanced TRIP effect.