The development of an efficient doped CeO2 material is an active area of intense research in environmental catalysis. In this study, we prepared highly promising Ce-Fe nano-oxides by a facile coprecipitation method and their catalytic performance was studied for CO oxidation. Various characterization techniques, namely, XRD, BET surface area, pore size distribution, Raman, FT-IR, TEM, H2-TPR, and XPS were used to correlate the structure-activity properties of the Ce-Fe catalysts. XRD results confirmed the formation of nanocrystalline Ce1-xFexO2-δ solid solution due to doping of Fe3+ into the CeO2 lattice. The BET surface area and lattice strain of CeO2 are significantly improved after the Fe-incorporation. Raman studies revealed the presence of abundant oxygen vacancies in the Ce-Fe sample. TEM images evidenced the formation of nanosized particles with an average diameter of 5-20 nm in the prepared samples. Interestingly, despite the thermal treatment at higher temperatures, the Ce-Fe sample showed remarkable reducible nature compared to pure CeO2 ascribed to existence of strong interaction between the CeO2 and FeOx. The synthesized Ce-Fe nano-oxides calcined at 773 K exhibited excellent CO oxidation performance (T50 = 480 K), with a huge difference of 131 K with respect to pure CeO2 (T 50 = 611 K). The outstanding activity of the Ce-Fe catalyst is mainly due to smaller crystallite size, facile reduction, enhanced lattice strain, and ample oxygen vacancies. The superior CO oxidation performance of Ce-Fe nano-oxides with the advantages of low cost and easy availability could make them potential alternatives to noble metal-based oxidation catalysts. © 2014 The Royal Society of Chemistry.