A colloidal solution of magnetic nanoparticles (MNPs) modified with biocompatible positively charged poly-L-lysine (PLL) with an oleate (OL) layer employed as an initial coating was produced as a potential MRI contrast agent. The effect of various PLL/MNPs’ mass ratios on the samples’ hydrodynamic diameter, zeta potential, and isoelectric point (IEP) was studied by the dynamic light-scattering method. The optimal mass ratio for MNPs’ surface coating was 0.5 (sample PLL0.5-OL-MNPs). The average hydrodynamic particle size in the sample of PLL0.5-OL-MNPs was 124.4 ± 1.4 nm, and in the PLL-unmodified nanoparticles, it was 60.9 ± 0.2 nm, indicating that the OL-MNPs’ surface became covered by PLL. Next, the typical characteristics of the superparamagnetic behavior were observed in all samples. In addition, the decrease in saturation magnetizations from 66.9 Am2/kg for MNPs to 35.9 and 31.6 Am2/kg for sample OL-MNPs and PLL0.5-OL-MNPs also confirmed successful PLL adsorption. Moreover, we show that both OL-MNPs and PLL0.5-OL-MNPs exhibit excellent MRI relaxivity properties and a very high r2(*)/r1 ratio, which is very desirable in biomedical applications with required MRI contrast enhancement. The PLL coating itself appears to be the crucial factor in enhancing the relaxivity of MNPs in MRI relaxometry.