In this paper, cobalt and nitrogen co-doped carbon nanotubes were successfully synthesized by a simple thermal treatment method with dicyandiamide and cobalt (II) chloride hexahydrate. The as-synthesized nanostructures presented excellent catalytic activity and stability toward oxygen reduction reaction in alkaline solution. Especially, when the molar ratio between dicyandiamide and cobalt (II) chloride hexahydrate was 22:1, the catalyst showed close onset potential, half-wave potentials and limiting current density comparing to the commercial platinum/carbon catalyst, which might be contributed to the formation of pyridinic and quaternary nitrogen functional groups during the thermal treatment. Moreover, the as-synthesized catalyst exhibited good tolerance to methanol crossover effect.