Although lithium-ion batteries are traditionally considered to be the most promising candidate for electrochemical energy storage owing to their relatively long cycle life and high energy efficiency, their limited energy density as well as high cost are still causing a bottleneck for their long-term applications. Alternatively, rechargeable Li-O2 batteries have the potential to practically provide 3-5 times the gravimetric energy density of conventional Li-ion batteries. However, the lack of advanced electrode design and efficient electrocatalysts for oxygen reduction-evolution reactions remains as one of the grand challenges before this technology can be commercialized. Among various catalyst formulations, nanocarbon composite materials have been recognized as the most promising ones for Li-O2 batteries because of their reasonable balance among catalytic activity, durability, and cost. In this perspective, the recent progress in the development of nanostructured carbon-based electrocatalysts for nonaqueous Li-O2 batteries is discussed, including metal-free carbon catalysts, transition-metal-nitrogen-carbon composite catalysts, and transition-metal-compounds/nanocarbon catalysts. The morphology-performance correlations of these catalysts are highlighted, aiming to provide guidance for rationally designing advanced catalysts.