We have investigated atomic structure and magnetism in Fe nanoparticles with a diameter of 2 nm embedded in a Pd matrix. The samples for these studies were prepared directly from the gas phase by co-deposition, using a gas aggregation source and an MBE-type source for the Fe nanoparticles and Pd matrix respectively. Extended absorption fine structure (EXAFS) measurements indicate that there is an appreciable degree of alloying at the nanoparticle/matrix interface; at dilute nanoparticle concentrations, more than half of the Fe atoms are alloyed with Pd. This leads to a core/shell structure in the embedded nanoparticles, with an FexPd1−x shell surrounding a reduced pure Fe core. Magnetism in the nanocomposite samples was probed by means of magnetometry measurements, which were interpreted in the light of their atomic structure. These point to a magnetized cloud of Pd atoms surrounding the embedded nanoparticles which is significantly larger than around single Fe atoms in Pd. The coercivities in the Fe/Pd nanocomposite samples are larger than in FexPd1−x atomic alloys of corresponding composition, which is consistent with exchange coupling between the magnetically harder and softer regions in the nanocomposite samples.