Iron nanoparticles are highly-effective magnetic nanoparticles for T2 magnetic resonance imaging (MRI). However, the stability of their magnetic properties is dependent on good protection of the iron core from oxidation in aqueous media. Here we report the synthesis of custom-synthesized phosphonate-grafted polyelectrolytes (PolyM3) of various chain lengths, for efficient coating of iron nanoparticles with a native iron oxide shell. The size of the nanoparticle-polyelectrolyte assemblies was investigated by transmission electron microscopy and dynamic light scattering, while surface attachment was confirmed by Fourier transform infrared spectroscopy. Low cytotoxicity was observed for each of the nanoparticle-polyelectrolyte (“Fe-PolyM3”) assemblies, with good cell viability (>80%) remaining up to 100 μg mL−1 Fe in HeLa cells. When applied in T2-weighted MRI, corresponding T2 relaxivities (r2) of the Fe-PolyM3 assemblies were found to be dependent on the chain length of the polyelectrolyte. A significant increase in contrast was observed when polyelectrolyte chain length was increased from 6 to 65 repeating units, implying a critical chain length required for stabilization of the α-Fe nanoparticle core.