Creating and maintaining precipitates coherent with the host matrix, under service conditions is one of the most effective approaches for successful development of alloys for high temperature applications; prominent examples include Ni- and Co-based superalloys and Al alloys. While ferritic alloys are among the most important structural engineering alloys in our society, no reliable coherent precipitates stable at high temperatures have been found for these alloys. Here we report discovery of a new, nano-sized superlattice (NSS) phase in ball-milled Fe alloys, which maintains coherency with the BCC matrix up to at least 913 °C. Different from other precipitates in ferritic alloys, this NSS phase is created by oxygen-ordering in the BCC Fe matrix. It is proposed that this phase has a chemistry of Fe3O and a D03 crystal structure and becomes more stable with the addition of Zr. These nano-sized coherent precipitates effectively double the strength of the BCC matrix above that provided by grain size reduction alone. This discovery provides a new opportunity for developing high-strength ferritic alloys for high temperature applications.