Density functional plane-wave calculations have been performed to investigate a series of ceria nanoparticles (CeO2-x)(n), n <or= 85. Strong correlation effects of the Ce f-electron introduced upon Ce4+ --> Ce3+ reduction have been accounted for through the use of an effective on-site Coulomb repulsive interaction within the so-called DFT+U approach. Twelve nanoparticles of up to 2 nm in diameter and of both cuboctahedral and octahedral forms are chosen as representative model systems. Energetic and structural effects of oxygen vacancy formation in these nanoparticles are discussed with respect to those in the bulk and on extended surfaces. We show that the average interatomic distances of the nanoparticles are most significantly affected by the creation of oxygen vacancies. The formation energies of non-stoichiometric nanoparticles (CeO2-x)(n) are found to scale linearly with the average coordination number of Ce atoms; where x < 0 species, containing partially reduced O atoms, are less stable. The stability of octahedral ceria particles at small sizes, and the predicted strong propensity of Ce cations to acquire a reduced state at lower coordinated sites, is supported by interatomic potential-based global optimisations probing the low energy isomers of the Ce19O32 nanoparticle.