Exchange-coupled fct-FePd/alpha-Fe nanocomposite magnets were fabricated by converting anisotropically phase-segregated Pd/gamma-Fe2O3 nanoparticles via the interfacial atom diffusion. The magnetically hard fct-FePd phases formed by the interdiffusion between alpha-Fe and fcc-Pd phases nearly preserve their sizes at the nanometer scale because they are surrounded by the alpha-Fe matrix. The VSM measurements reveal that the exchange coupling between the soft and hard phases has been realized.