The development of unique, reliable, and scalable synthesis strategies for producing heteroatom-doped nanostructured carbon materials with improved activity toward the electrochemical oxygen reduction reaction (ORR) occurring in metal-air batteries and fuel cells presents an intriguing technological challenge in the field of catalysis. Herein, we prepare unique graphene-carbon nanotube composites (GC) doped sequentially with both nitrogen and sulfur (GC-NLS) and subject them to extensive physicochemical characterization and electrochemical evaluation toward the ORR in an alkaline electrolyte. GC-NLS provides ORR onset potential increases of SO and 70 mV in comparison to those of dual-doped individual graphene and carbon nanotubes, respectively. This highlights the significant synergistic effects that arise because of the nanocomposite arrangement, consisting of highly graphitized carbon nanotubes assembled on the surface of graphene sheets. The addition of sulfur as a co-dopant is also highly beneficial, providing an 80 mV increase in the ORR onset potential in comparison to that of GC nanocomposites doped with only nitrogen. Excellent electrochemical stability of GC-NLS is also observed through 5000 electrode potential cycles, indicating the promising potential of this new class of dual-doped GC nanocomposites as ORR catalysts.