The local structure of the M-O bond in CeO2-ZrO2 mixed oxides is investigated with the aim of finding a correlation between structural parameters and oxygen exchange properties. It is found that insertion of ZrO2 into the CeO2 lattice strongly perturbs the symmetry of the M-O bond. As the content of CeO2 in CeO2-ZrO2 solid solution is increased from 20 to 80 mol%, tetragonal, (t, t′, t″) and cubic phases are formed. The local symmetry of the Zr-O bond is strongly perturbed by the increase in CeO2 content while no significant modification of the first Ce-O coordination sphere is found, except for lengthening of the Ce-O bond consistent with lattice parameter increase. The perturbation of the Zr-O coordination sphere, which leads to highly disordered oxygen in the lattice, is indicated as responsible for the high oxygen mobility in CeO2-ZrO2 mixed oxides.