Zn-air batteries are highly attractive for direct chemical-to-electrical energy conversion and for solving the energy crisis and environmental problems. Designing efficient oxygen electrodes has been considered one of the most critical steps in the development of advanced Zn-air batteries because of the sluggish kinetics of the oxygen reduction reaction and the oxygen evolution reaction. In recent years, nanostructured carbon-based electrodes with large surface areas, efficient oxygen-catalytic centers, and hierarchically porous matrices have provided significant opportunities to optimize the performance of the oxygen electrodes in both primary and rechargeable Zn-air batteries. In this review, we provide a comprehensive summary of the reported nanostructured carbon-based electrodes for advanced Zn-air batteries in terms of tailoring the oxygen-catalytic sites and designing carbon supports. The versatile synthetic strategies, characterization methods, and in-depth understanding of the relationships between the oxygen-catalytic sites/nanostructures and the oxygen electrode performance are systematically summarized. Furthermore, we also briefly outline recent progress in engineering flexible and high-power Zn-air batteries. Ultimately, a thorough discussion of current primary challenges and future perspectives on the rational design of nanostructured carbon-based oxygen electrodes is given, thus providing inspiration for the future prosperity of fast-kinetic and efficient Zn-air batteries in a broad range of energy fields.