Temperature-programmed reduction in a H-2/Ar mixture of Rh-loaded CeO2-ZrO2 solid solutions with a ZrO2 content varying between 10 and 90% mol and of monoclinic, tetragonal, and cubic structures is reported. It is shown that incorporation of ZrO2 into a solid solution with CeO2 strongly promotes bulk reduction of the Rh-loaded solid solutions in comparison to a Rh/CeO2 sample. The promotion of the bulk reduction results in high oxygen storage capacity (OSC) as measured by oxygen uptake. A structural dependence of both reduction and oxidation processes is observed which is attributed to a higher oxygen mobility in the cubic structure compared to the tetragonal and monoclinic ones.