Designing a highly efficient catalyst is essential to improve the electrochemical performance of Li-O2 batteries for long-term cycling. Furthermore, these batteries often show significant capacity fading due to the irreversible reaction characteristics of the Li2O2 product. To overcome these limitations, we propose a bifunctional composite catalyst composed of electrospun one-dimensional (1D) Co3O4 nanofibers (NFs) immobilized on both sides of the 2D nonoxidized graphene nanoflakes (GNFs) for an oxygen electrode in Li-O2 batteries. Highly conductive GNFs with noncovalent functionalization can facilitate a homogeneous dispersion in solution, thereby enabling simple and uniform attachment of 1D Co3O4 NFs on GNFs without restacking. High first discharge capacity of 10 500 mAh/g and superior cyclability for 80 cycles with a limited capacity of 1000 mAh/g were achieved by (i) improved catalytic activity of 1D Co3O4 NFs with large surface area, (ii) facile electron transport via interconnected GNFs functionalized by Co3O4 NFs, and (iii) fast O2 diffusion through the ultrathin GNF layer and porous Co3O4 NF networks.