Magnetite nanoparticles (MNPs) coated with poly(acrylic acid-co-maleic acid) polyelectrolyte (PAM) have been prepared with the aim of improving colloidal stability of core-shell nanoparticles for biomedical applications and enhancing the durability of the coating shells. FTIR-ATR measurements reveal two types of interaction of PAM with MNPs: hydrogen bonding and inner-sphere metal-carboxylate complex formation. The mechanism of the latter is ligand exchange between uncharged -OH groups of the surface and -COO- anionic moieties of the polyelectrolyte as revealed by adsorption and electrokinetic experiments. The aqueous dispersion of PAM@MNP particles (magnetic fluids - MFs) tolerates physiological salt concentration at composition corresponding to the plateau of the high-affinity adsorption isotherm. The plateau is reached at small amount of added PAM and at low concentration of nonadsorbed PAM, making PAM highly efficient for coating MNPs. The adsorbed PAM layer is riot desorbed during dilution. The performance of the PAM shell is superior to that of poly(acrylic acid) (PAA), often used in biocompatible MFs. This is explained by the different adsorption mechanisms; metal-carboxylate cannot form in the case of PAA. Molecular-level understanding of the protective shell formation on MNPs presented here improves fundamentally the colloidal techniques used in core-shell nanoparticle production for nanotechnology applications.