For supported catalysts based on highly-priced noble metals the maximum catalytic efficiency per metal atom is highly desired. In this work, Rh-doped CeO2 systems were studied as potential catalysts for low-temperature NO reduction by CO. Thermal and redox treatments allowed varying the Rh oxidation state and the size of rhodium particles formed on CeO2 surface. By combination of surface and bulk sensitive physicochemical techniques the structure-activity correlations were established. Initial Rh-doped CeO2 catalysts contained Rh3+ species ionically dispersed in CeO2 lattice and showed activity in CO + NO reaction already at room temperature. Reduction treatment of Rh3+-CeO2 catalysts resulted in the formation of rhodium particles of ~1 nm in size on the reduced ceria surface. The catalytic characteristics of the initial and reduced samples were comparable, indicating the close nature of the active sites and their dynamic formation directly under the reaction conditions. Calcination of Rh3+-CeO2 sample at T > 800°С resulted in formation of rhodium oxide nanoparticles on the ceria surface. Such Rh2О3/CeO2 catalysts showed activity only at T > 200°С. Their activity in 100–200 °C temperature range could be substantially improved by the reduction treatment. The oxygen vacancies of СеО2 and small Rhn 0 particles proved to be essential for the catalytic activity below 100 °C.