We have studied (001) surface terminated cerium oxide nanoparticles grown on a ruthenium substrate using physical vapor deposition. Their morphology, shape, crystal structure, and chemical state are determined by low-energy electron microscopy and micro-diffraction, scanning probe microscopy, and synchrotron-based X-ray absorption spectroscopy. Square islands are identified as CeO2 nanocrystals exhibiting a (001) oriented top facet of varying size; they have a height of about 7 to 10 nm and a side length between about 50 and 500 nm, and are terminated with a p(2 × 2) surface reconstruction. Micro-illumination electron diffraction reveals the existence of a coincidence lattice at the interface to the ruthenium substrate. The orientation of the side facets of the rod-like particles is identified as (111); the square particles are most likely of cuboidal shape, exhibiting (100) oriented side facets. The square and needle-like islands are predominantly found at step bunches and may be grown exclusively at temperatures exceeding 1000 °C.