We investigated the oxygen-reduction reaction (ORR) on Pd monolayers on various surfaces and on Pd alloys to obtain a substitute for Pt and to elucidate the origin of their activity. The activity of Pd monolayers supported on Ru(0001), Rh(111), Ir(111), Pt(111), and Au(111) increased in the following order:  Pd/Ru(0001) < Pd/Ir(111) < Pd/Rh(111) < Pd/Au(111) < Pd/Pt(111). Their activity was correlated with their d-band centers, which were calculated using density functional theory (DFT). We found a volcano-type dependence of activity on the energy of the d-band center of Pd monolayers, with Pd/Pt(111) at the top of the curve. The activity of the non-Pt Pd2Co/C alloy electrocatalyst nanoparticles that we synthesized was comparable to that of commercial Pt-containing catalysts. The kinetics of the ORR on this electrocatalyst predominantly involves a four-electron step reduction with the first electron transfer being the rate-determining step. The downshift of the d-band center of the Pd “skin”, which constitutes the alloy surface due to the strong surface segregation of Pd at elevated temperatures, determined its high ORR activity. Additionally, it showed very high methanol tolerance, retaining very high catalytic activity for the ORR at high concentrations of methanol. Provided its stability is satisfactory, this catalyst might possibly replace Pt in fuel-cell cathodes, especially those of direct methanol oxidation fuel cells (DMFCs).