Carbon-based nanomaterials, such as carbon-encapsulated magnetic nanoparticles (CEMNP, core@shell), show a wide range of desirable properties for applications in the biomedical field (clinical MRI, hyperthermia), for energy production and storage (hydrogen storage), for the improvement of electronic components and for environmental applications (water-treatment). However, this kind of nanoparticle tends to aggregate in water suspensions. This often hampers the processability of the suspensions and presents an obstacle to their application in many fields. Here the stabilisation of core-shell Fe-C nanoparticles by surface adsorbed polyvinyl-alcohol (PVA) is presented. Different PVA/CEMNP mass ratios (9, 36, 144 and 576 w/w) were studied. Several characterisation techniques were used in order to determine the size distribution of the particles and to optimize the PVA/CEMNP ratio. A good colloidal stability was obtained for spherical nanoparticles about 50 nm in diameter containing several superparamagnetic Fe cores. The nanoparticles were found to be isolated and well dispersed in solution. The use of PVA for coating carbon-encapsulated Fe nanoparticles does not only result in a good colloidal stability in aqueous suspensions, but the resulting particles also show low cytotoxicity and an interesting cell internalization behaviour. The simple stabilization method developed here can likely be extended to other core@shell nanoparticle systems as well as other carbon-based nanomaterials in the future.