Sulfur-doped graphene (SG) is prepared by a thermal shock/quench anneal process and investigated as a unique Pt nanoparticle support (Pt/SG) for the oxygen reduction reaction (ORR). Particularly, SG is found to induce highly favorable catalyst-support interactions, resulting in excellent half-cell based ORR activity of 139 mA mg(Pt)(-1) at 0.9 V vs RHE, significant improvements over commercial Pt/C (121 mA mg(Pt)(-1)) and Pt-graphene (Pt/G, 101 mA mg(Pt)(-1)). Pt/SG also demonstrates unprecedented stability, maintaining 87% of its electrochemically active surface area following accelerated degradation testing. Furthermore, a majority of ORR activity is maintained, providing 108 mA mg(Pt)(-1), a remarkable 171% improvement over Pt/C (39.8 mA mg(Pt)(-1)) and an 89% improvement over Pt/G (57.0 mA mg(Pt)(-1)). Computational simulations highlight that the interactions between Pt and graphene are enhanced significantly by sulfur doping, leading to a tethering effect that can explain the outstanding electrochemical stability. Furthermore, sulfur dopants result in a downshift of the platinum d-band center, explaining the excellent ORR activity and rendering SG as a new and highly promising class of catalyst supports for electrochemical energy technologies such as fuel cells.