Doping CeO2 with Pd or Pt increases the oxygen storage capacity (OSC) and catalytic activity of this environmentally important material. To date, however, an understanding of the mechanism underlying this improvement has been lacking. We present a density functional theory analysis of Pd- and Pt-doped CeO2, and demonstrate that the increased OSC is due to a large displacement of the dopant ions from the Ce lattice site. Pd(II)/Pt(II) (in a d8 configuration) moves by ~1.2 Å to adopt a square-planar coordination due to crystal field effects. This leaves three three-coordinate oxygen atoms that are easier to remove, and which are the source of the increased OSC. These results highlight the importance of rationalizing the preferred coordination environments of both dopants and host cations when choosing suitable dopants for next generation catalysts.