Soft magnetic alloys at the nanoscale level have long generated a vivid interest as candidate materials for technological and biomedical purposes. Consequently, controlling the structure of bimetallic nanoparticles in order to optimize their magnetic properties, such as high magnetization and low coercivity, can significantly boost their potential for related applications. However, traditional synthesis methods stumble upon the long standing challenge of developing true nanoalloys with effective control over morphology and stability against oxidation. Herein, we report on a single-step approach to the gas phase synthesis of soft magnetic bimetallic iron aluminide nanoparticles, using a versatile co-sputter inert gas condensation technique. This method allowed for precise morphological control of the particles; they consisted of an alloy iron aluminide crystalline core (DO3 phase) and an alumina shell, which reduced inter-particle interactions and also prevented further oxidation and segregation of the bimetallic core. Remarkably, the as-deposited alloy nanoparticles show interesting soft magnetic properties, in that they combine a high saturation magnetization (170 emu/g) and low coercivity (less than 20 Oe) at room temperature. Additional functionality is tenable by modifying the surface of the particles with a polymer, to ensure their good colloidal dispersion in aqueous environments.