Manipulating structure, defects and composition of a material at the atomic scale for enhancing its physical or mechanical properties is referred to as nanostructuring. Here, by combining advanced microscopy techniques, we unveil how formation of highly regular nano-arrays of nanoparticles doubles the strength of an Fe-based alloy, doped with Ti, Mo, and V, from 500 MPa to 1 GPa, upon prolonged heat treatment. The nanoparticles form at moving heterophase interfaces during cooling from the high-temperature face-centered cubic austenite to the body-centered cubic ferrite phase. We observe MoC and TiC nanoparticles at early precipitation stages as well as core-shell nanoparticles with a Ti-C rich core and a Mo-V rich shell at later precipitation stages. The core-shell structure hampers particle coarsening, enhancing the material’s strength. Designing such highly organized metallic core-shell nanoparticle arrays provides a new pathway for developing a wide range of stable nano-architectured engineering metallic alloys with drastically enhanced properties.