Partial substitution of Ce4+ by Nb5+ is possible in CeO2 by coinclusion of Na+ to balance the charge, via hydrothermal synthesis in sodium hydroxide solution. Pair distribution function analysis using reverse Monte Carlo refinement reveals that the small pentavalent substituent resides in irregular coordination positions in an average fluorite lattice, displaced away from the ideal cubic coordination toward four oxygens. This results in under-coordinated oxygen, which explains significantly enhanced oxygen storage capacity of the materials of relevance to redox catalysis used in energy and environmental applications.