Graphene based materials have attracted tremendous attention, attributed to their unique physicochemical properties and versatile applications. In general, these materials are very promising candidates for the development of next-generation electrochemical systems for energy and environmental technology and sensor applications. In particular, graphene-metal oxide nanohybrid materials have been introduced as a new basis for preparation of low cost and highly efficient electrocatalysts for energy storage and conversion as well as for electrochemical sensing applications. By combining graphene with specific metal oxide nanostructures, resulting nanohybrid materials can play a significant role in the cutting-edge development of state-of-the-art electrocatalysts using commercially available and low-cost precursors. Herein, we review the mostly recent advances in the development of noble metal free graphene supported electrocatalysts. This review includes an introduction to graphene-metal oxide based nanohybrid materials, different synthetic strategies for the preparation of graphene/metal oxide nanocomposites and their structural characterization, and an overview of various electrochemical applications. The current challenges and possible future directions are briefly discussed, prior to conclusions.