High-pressure angle-dispersive x-ray diffraction measurements have been performed on bulk and nanocrystalline cubic CeO2 with mean sizes of 4.7 and 5.6 nm. It is found that the compressibility of the nanocrystals is lower than the bulk when a threshold pressure is reached. This critical pressure is found to be 10 GPa for 4.7 nm and 16 GPa for 5.6 nm CeO2 nanocubes. The particle size dependence of the threshold pressure for the hardening of CeO2 nanoparticles is quite unusual. First-principles electronic calculations show that the increased bulk modulus of the nanocrystal is due to the strengthening of the surface Ce-O bonds resulting in a much larger shear modulus than in the bulk and consequently hardening the shell surface.