We report a facile approach for the in situ synthesis of very small iron oxide nanoparticles on the surface of high-quality graphene sheets. Our synthetic strategy involved the direct, liquid-phase exfoliation of highly crystalline graphite (avoiding any oxidation treatment) and the subsequent chemical functionalization of the graphene sheets via the well-established 1,3-dipolar cycloaddition reaction. The resulting graphene derivatives were employed for the immobilization of the nanoparticle precursor (Fe cations) at the introduced organic groups by a modified wet-impregnation method, followed by interaction with acetic acid vapours. The final graphene-iron oxide hybrid material was achieved by heating (calcination) in an inert atmosphere. Characterization by X-ray diffraction, transmission electron and atomic force microscopy, Raman and X-ray photoelectron spectroscopy gave evidence for the formation of rather small (<12 nm), spherical, magnetite-rich nanoparticles which were evenly distributed on the surface of few-layer (<1.2 nm thick) graphene. Due to the presence of the iron oxide nanoparticles, the hybrid material showed a superparamagnetic behaviour at room temperature.