CeO2-ZrO2 solid solutions supported with Rh and Pt are investigated as catalysts for reduction of NO by CO. The incorporation of ZrO2 into the CeO2 framework strongly promotes the reduction of Ce4+ in the bulk of the support. The effects of the reduction temperature are investigated and it is shown that when bulk oxygen vacancies are formed in the reduced CeO2-ZrO2 solid solution, NO is efficiently decomposed on the support to give N2O and N-2. The presence of bulk oxygen vacancies is indicated as the driving force for NO dissociation, suggesting their indirect participation in the catalytic cycle.