The average structure and the local structure of nanocrystalline Rh-doped CeO2 catalysts, prepared using a co-precipitation method, were studied using a set of structural (PDF, HRTEM, XRD) and spectral (XPS, Raman spectroscopy) methods. The samples with Rh content less than 10 wt%, calcined at 450 °C, were homogeneous solid solutions. A comparison of the experimental results and Pair distribution function (PDF) modeling data showed that Rh3+ substitutes Ce4+ ions in the fluorite phase. Charge equilibrium is obtained by the oxygen vacancy for each Rh3+ cation introduced into the ceria cell. The solid solution demonstrated high catalytic activity in low-temperature CO oxidation (LTO CO). The solid solutions were stable only in a nanocrystalline state and decomposed upon thermal treatment. The calcination of the solid solution at T > 450 °C results in a decrease in the catalytic activity that is accompanied by Rh association in the subsurface area and strong distortion of the anionic subcell. At T = 800 °C α-Rh2O3 nanoparticles are formed on the surface of the fluorite phase. The XRD-detectable Rh oxide phases are formed after calcination at 1000 °C. However, some parts of Rh within the subsurface RhxCe1-xO2-δ solid solution remain and they preserve catalytic properties for low-temperature oxidation.