AuFe nanoparticles with mean diameters d p = 13.2 nm have been prepared by inert-gas condensation. Conventional and high-resolution transmission electron microscopy and energy-dispersive x-ray spectroscopy investigations show that the particles are mostly icosahedra. Scanning transmission electron microscopy-energy-dispersive x-ray spectroscopy and scanning transmission electron microscopy-electron energy-loss spectroscopy show that the as-grown particles exhibit a core-shell structure. The shell is mainly composed of an amorphous FeO layer. Although Fe and Au are immiscible in the bulk, the particle cores are found to be homogeneously mixed at the atomic level with a local composition of around Au84Fe16 (at.%). AuFe nanoparticles exhibit a complex magnetic structure in which the core behaves as a spin glass with a freezing temperature of 35 K, whereas the amorphous FeO shell behaves as a ferro-ferrimagnetic system. On annealing above 300 °C, the AuFe icosahedra phases separate into their elemental constituents. Hence the as-grown AuFe icosahedra are metastable, thereby implying that the bulk phase diagram also applies for nanoscopic materials.