Combustion catalysts have been extensively explored to reduce the emission of hydrocarbons that are capable of triggering photochemical smog and greenhouse effect. Palladium as the most active material is widely applied in exhaust catalytic converter and combustion units, but its high capital cost stimulates the tremendous research on non-noble metal candidates. Here we fabricate highly defective cobalt oxide nanocrystals via a controllable oxidation of carbon-encapsulated cobalt nanoparticles. Strain gradients induced in the nanoconfined carbon shell result in the formation of a large number of active sites featuring a considerable catalytic activity for the combustion of a variety of hydrocarbons (methane, propane and substituted benzenes). For methane combustion, the catalyst displays a unique activity being comparable or even superior to the palladium ones.