Ultra-small magnetic nanoparticles consisting of NiCo and FeNi alloys enclosed within graphitic shells (NiCo/G and FeNi/G) have been synthesized. The particles, which retained the face centered cubic (fcc) symmetry of the original bulk metals, together with the graphitic coating were characterized by means of aberration corrected scanning transmission electron microscopy (STEM), obtaining mean particle sizes of 2.6 nm and 6.2 nm for NiCo/G and FeNi/G, respectively. Due to the enhancement of the thermal stability by the graphite shell, the graphite coated FeNi and NiCo were stable under oxygen atmosphere up to 170 °C. The effectiveness of the graphite shell was confirmed when unprotected bimetallic FeNi and NiCo were prepared and chemical characterization revealed that more than 60 at.% of the samples was oxygen due to the massive oxidation of the bimetallic nanoparticles.