Several nanosized catalysts Co3O4–CeO2 with varying compositions were synthesized by a surfactant-template method and further promoted by a small amount of Pd (0.5 wt%). These catalysts exhibit uniform mesoporous structure and high surface area (>100 m2 g−1). The Co3O4 crystallites in these catalysts are encapsulated by nanosized CeO2 with only a small fraction of Co ions exposing on the surface and strongly inter- acting with CeO2. Such structure maximizes the interaction between Co3O4 and CeO2 in three dimensions, resulting in unique redox properties. The introduction of Pd prominently enhances both the reduction and oxidation performance of the catalysts, due to hydrogen or oxygen spillover. These catalysts prepared by surfactant-template method exhibit excellent oxidation performance, especially the ones promoted with Pd, which show markedly enhanced CO oxidation activity even at room temperature. Based upon the results of structural properties, redox behaviors and in situ DRIFTS study, two different reaction pathways over Co3O4–CeO2 and Pd/Co3O4–CeO2 are proposed.