Bifunctional materials able to catalyze both the oxygen reduction (ORR) and the oxygen evolution (OER) reactions in alkaline media are still a challenge for the progress of energy conversion and storage devices such as metal-air batteries or unitized regenerative fuel cells. In this work, carbon nanofibers synthesized by electrospinning are modified with a combination of cobalt oxide and metallic cobalt (CoO-Co/CNF) and studied as a bifunctional air electrode for metal-air batteries. The performance of CoO-Co/CNF for both reactions is compared with state-of-the-art catalysts such as Pt/C and IrO2. The combination of cobalt oxide and metallic cobalt, finely distributed on the surface of graphitic carbon nanofibers, leads to a bifunctional catalyst with a half-wave potential for the ORR slightly better than Pt/C and a reversibility (ΔEOER-ORR) of 809 mV. The stability of CoO-Co/CNF is assessed by means of different stress tests: polarizations at high electrochemical potentials (2 V vs. RHE), rapid charge-discharge cycles at ±80 mA cm−2 and long durability tests by charging for 12 h at 60 mA cm−2 and discharging for 8 h at −80 mA cm−2. CoO-Co/CNF shows a remarkable stability, maintaining, at least, an 82% of its performance for the ORR after the stress tests, even when cycled for more than 100 h.