Collective interstitial ordering is at the core of martensite formation in Fe-C-based alloys, laying the foundation for high-strength steels. Even though this ordering has been studied extensively for more than a century, some fundamental mechanisms remain elusive. Here, we show the unexpected effects of two correlated phenomena on the ordering mechanism: anharmonicity and segregation. The local anharmonicity in the strain fields induced by interstitials substantially reduces the critical concentration for interstitial ordering, up to a factor of three. Further, the competition between interstitial ordering and segregation results in an effective decrease of interstitial segregation into extended defects for high interstitial concentrations. The mechanism and corresponding impact on interstitial ordering identified here enrich the theory of phase transitions in materials and constitute a crucial step in the design of ultra-high-performance alloys.