The combination of different phase constituents to realize a mechanical composite effect for superior strength-ductility synergy has become an important strategy in microstructure design in advanced high-strength steels. Introducing multiple phases in the microstructure essentially produces a large number of phase boundaries. Such hetero-interfaces affect the materials in various aspects such as dislocation activity and damage formation. However, it remains a question whether the characteristics of phase boundaries, such as their chemical decoration states, would also have an impact on the mechanical behavior in multiphase steels. Here we reveal a phase boundary segregation-induced strengthening effect in ultrafine-grained duplex medium-Mn steels. We found that the carbon segregation at ferrite-austenite phase boundaries can be manipulated by adjusting the cooling conditions after intercritical annealing. Such phase boundary segregation in the investigated steels resulted in a yield strength enhancement by 100–120 MPa and simultaneously promoted discontinuous yielding. The sharp carbon segregation at the phase boundaries impeded interfacial dislocation emission, thus increasing the stress required to activate such dislocation nucleation process and initiate plastic deformation. This observation suggests that the enrichment of carbon at the phase boundaries can enhance the energy barrier for dislocation emission, which provides a favorable condition for plastic flow avalanches and thus discontinuous yielding. These findings extend the current understanding of the yielding behavior in medium-Mn steels, and more importantly, shed light on utilizing and manipulating phase boundary segregation to improve the mechanical performance of multiphase metallic materials.