Gd-based complexes are widely used as magnetic resonance imaging (MRI) contrast agents. The safety of previously approved contrast agents is questionable and is being re-assessed. The main causes of concern are possible gadolinium deposition in the brain and the development of systemic nephrogenic fibrosis after repeated use of MRI contrasts. Thus, there is an urgent need to develop a new generation of MRI contrasts that are safe and that have high selectivity in tissue accumulation with improved local contrast. Here, we report on a new type of theranostic MRI contrast, namely dextran stabilised, gadolinium doped cerium dioxide nanoparticles. These ultra-small (4-6 nm) Ce0.9Gd0.1O1.95 nanoparticles have been shown to possess excellent colloidal stability and high r1-relaxivity (3.6 mM-1 s-1). They are effectively internalised by human normal and cancer cells and demonstrate dose-dependent selective cytotoxicity to cancer cells.