Carbides of groups IV through VI (Ti, V and Cr groups) have long been proposed as substitutes for noble metal-based electrocatalysts in polymer electrolyte fuel cells. However, their catalytic activity has been extremely limited because of the low density and stability of catalytically active sites. Here we report the excellent performance of a niobium-carbon structure for catalysing the cathodic oxygen reduction reaction. A large number of single niobium atoms and ultra small clusters trapped in graphitic layers are directly identified using state-of-the-art aberration-corrected scanning transmission electron microscopy. This structure not only enhances the overall conductivity for accelerating the exchange of ions and electrons, but it suppresses the chemical/thermal coarsening of the active particles. Experimental results coupled with theory calculations reveal that the single niobium atoms incorporated within the graphitic layers produce a redistribution of d-band electrons and become surprisingly active for O2 adsorption and dissociation, and also exhibit high stability.