The impact of graphene substrate-Pd nanoparticle interaction on the O, OH, and OOH adsorption that is directly related to the electrocatalytic performance of these composites in oxygen reduction reaction (ORR) has been investigated by first-principles-based calculations. The calculated binding energy of a Pd 13 nanoparticle on a single vacancy graphene is as high as -6.10 eV, owing to the hybridization between the dsp states of the Pd particles with the sp 2 dangling bonds at the defect sites. The strong interaction results in the averaged d-band center of the deposited Pd nanoparticles shifted away from the Fermi level from -1.02 to -1.45 eV. Doping the single vacancy graphene with B or N will further tune the average d-band center and also the activity of the composite toward O, OH, and OOH adsorption. The adsorption energies of O, OH, and OOH are reduced from -4.78, -4.38, and -1.56 eV on the freestanding Pd 13 nanoparticle to -4.57, -2.66, and -1.39 eV on Pd 13/single vacancy graphene composites, showing that the defective graphene substrate will not only stabilize the Pd nanoparticles but also reduce the adsorption energies of the O-containing species to the Pd particle, and so as the poisoning of the ORR active sites. © 2011 American Chemical Society.