A novel synthesis procedure is devised to obtain nitrogen-doping in hydrogen-exfoliated graphene (HEG) sheets. An anionic polyelectrolyte-conducting polymer duo is used to form a uniform coating of the polymer over graphene sheets. Pyrolysis of graphene coated with polypyrrole, a nitrogen-containing polymer, in an inert environment leads to the incorporation of nitrogen atoms in the graphene network with simultaneous removal of the polymer. These nitrogen-doped graphene (N-HEG) sheets are used as catalyst support for dispersing platinum and platinum-cobalt alloy nanoparticles synthesized by the modified-polyol reduction method, yielding a uniform dispersion of the catalyst nanoparticles. Compared to commercial Pt/C electrocatalyst, Pt-Co/N-HEG cathode electrocatalyst exhibits four times higher power density in proton exchange membrane fuel cells, which is attributed to the excellent dispersion of Pt-Co alloy nanoparticles on the N-HEG support, the alloying effect of Pt-Co, and the high electrocatalytic activity of the N-HEG support. A stability study shows that Pt/N-HEG and Pt-Co/N-HEG cathode electrocatalysts are highly stable in acidic media. The study shows two promising electrocatalysts for proton exchange membrane fuel cells, which on the basis of performance and stability present the possibility of replacing contemporary electrocatalysts. A novel method for the synthesis of Pt-Co alloy nanoparticles dispersed on nitrogen-doped graphene is developed. The as-prepared electrocatalysts show excellent oxygen reduction reaction (ORR) activity and stability in acidic medium for proton exchange membrane fuel cell (PEMFC) applications due to the high dispersion and alloying effect of Pt-Co, along with the inherent electrocatalytic activity of nitrogen-doped graphene as the supporting material. Copyright © 2012 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.