A series of ceria nanocatalysts have been prepared to study the structure dependency of the CO oxidation reaction. The ceria samples with well-defined nanostructures (nanocubes/Ce-NC and nanorods/Ce-NR) have been prepared using the hydrothermal method. Mesoporous ceria (Ce-MES) and ceria synthesized with solution combustion technique (Ce-SCS) have also been prepared for comparison. The lowest CO oxidation temperature has been reached by using ceria nanocubes (Ce-NC). This high activity draws immense contributions from the highly reactive (100) and (110) surfaces of the truncated nanocubes. The Ce-MES and Ce-SCS samples, despite their high surface areas, are unable to outdo the activity of Ce-NC and Ce-NR due to the abundant presence of (111) crystalline planes. This finding confirms the structure sensitivity of CO oxidation reaction catalyzed with ceria.