The advances in cost effective, highly active and stable electrocatalysts for the oxygen reduction reaction (ORR) and the oxygen evolution reaction (OER) remain the major issues for the commercialization of metal air-batteries and alkaline fuel cells. In this aspect, a facile hydrothermal route was developed to prepare nonprecious metal electrocatalysts including pristine MoO3 rods, nanospheres, and their hybrids with reduced graphene oxide (rGO). This is the first report of the use of rGO coupled with hexagonal MoO3 nanocrystals that act as both ORR and OER catalysts. The rGO-MoO3 sphere hybrid catalyst exhibited excellent catalytic activity toward both the ORR and OER compared to pristine MoO3 rods, MoO3 spheres and rGO-MoO3 rods. In addition, the rGO-MoO3 nanosphere hybrid exhibited excellent catalytic activity, long-term durability, and CO tolerance compared to a high quality commercial Pt/C catalyst. This makes the GMS hybrid composite a highly promising candidate for high-performance non-precious metal-based bi-functional electrocatalysts with low cost and high efficiency for electrochemical energy conversion. The enhanced activity of the rGO-MoO3 nanosphere hybrid is due mainly to the enhanced structural openness in the tunnel structure of the hexagonal MoO3 when it is coupled with rGO.