Co-Ce-O composite oxides with high surface areas were firstly prepared by a modified citrate sol-gel method with N-2 thermal treatment prior to calcination in air. The prepared Co-Ce-O catalysts have higher Brunauer-Emmett-Teller surface areas than those prepared by conventional calcination in air, and thus exhibit more effective catalytic activities. Adding CeO2 into Co3O4 can not only increase the activity of Co3O4 but also greatly enhance its thermal stability. When the bulk atomic ratio of Co/Ce is 3/1, Co-Ce-O composite oxide possesses the best activity and stability for the methane combustion.