A facile hydrothermal route has been developed to prepare graphene–Co3O4 nanocomposites. The graphene–Co3O4 nanocomposite catalyst demonstrates an excellent catalytic activity toward oxygen-reduction reaction including a considerably more positive half-wave potential (−0.23 V) than that of pristine graphene (−0.39 V), as well as higher cathodic currents. More importantly, this catalyst shows better long-term durability than the commercial Pt/C catalyst in an alkaline solution. The preliminary results indicate that the graphene–Co3O4 nanocomposite is an efficient and stable bifunctional catalyst for Li–air batteries and may be an alternative to the high-cost commercial Pt/C catalyst for the ORR/OER in alkaline solutions.