Single-crystalline and uniform nanopolyhedra, nanorods, and nanocubes of cubic CeO2 were selectively prepared by a hydrothermal method at temperatures in the range of 100-180 degrees C under different NaOH concentrations, using Ce(NO3)3 as the cerium source. According to high-resolution transmission electron microscopy, they have different exposed crystal planes: {111} and {100} for polyhedra, {110} and {100} for rods, and {100} for cubes. During the synthesis, the formation of hexagonal Ce(OH)3 intermediate species and their transformation into CeO2 at elevated temperature, together with the base concentration, have been demonstrated as the key factors responsible for the shape evolution. Oxygen storage capacity (OSC) measurements at 400 degrees C revealed that the oxygen storage takes place both at the surface and in the bulk for the as-obtained CeO2 nanorods and nanocubes, but is restricted at the surface for the nanopolyhedra just like the bulk one, because the {100}/{110}-dominated surface structures are more reactive for CO oxidation than the {111}-dominated one. This result suggests that high OSC materials might be designed and obtained by shape-selective synthetic strategy.