Exploring an inexpensive, active and stable electrocatalyst as an alternative to expensive Pt for the oxygen reduction reaction (ORR), porous Co-Mo-ON alloy nanodendrites supported on nitrogen-doped graphene (Co-Mo-ON/NG) have been synthesized by a two-step solid state heating method. The Co-Mo-ON/NG nanodendrites offer high ORR activity and superior electrochemical stability both in acidic and alkaline media. This superiority is due to the synergistic effect of NG, enhanced catalytic efficiency by Mo, highly active intrinsic surface area and exposure of catalytic facets of nanodendritic morphology towards the ORR. The Co-Mo-ON/NG nanodendrites show a 4e - ORR process with 0.710 V and 0.915 V onset potentials in 0.5 M H 2 SO 4 and 0.1 M KOH, respectively. The Co-Mo-ON/NG nanodendrites show extreme electrochemical stability in terms of 96% and 97% current retention for 40000 s in both acidic and alkaline media, respectively, long term durability for continuous 2000 cycles and greater resistance to methanol than the commercial Pt/C catalyst. Furthermore, Mo-ON/NG, Co-ON/NG, and Co-Mo-ON are also tested to evaluate the effect of Mo-doping and NG on the electrocatalytic activity of Co-Mo-ON/NG nanodendrites. Owing to their low cost, easy synthesis, outstanding ORR performance, and extreme durability, Co-Mo-ON/NG nanodendrites emerged as a promising non-precious and highly stable ORR electrocatalyst in fuel cell applications.