The discovery of more efficient, economical, and selective catalysts for oxidative dehydrogenation is of immense economic importance. However, the temperatures required for this reaction are typically high, often exceeding 400 °C. Herein, we report the discovery of subnanometer sized cobalt oxide clusters for oxidative dehydrogenation of cyclohexane that are active at lower temperatures than reported catalysts, while they can also eliminate the combustion channel. These results found for the two cluster sizes suggest other subnanometer size (CoO)x clusters will also be active at low temperatures. The high activity of the cobalt clusters can be understood on the basis of density functional studies that reveal highly active under-coordinated cobalt atoms in the clusters and show that the oxidized nature of the clusters substantially decreases the binding energy of the cyclohexene species which desorb from the cluster at low temperature.