Graphene-supported (40-x) wt% Pd x wt% Co (0≤x≤13.33) alloys/composites have been prepared by a microwave-assisted polyol reduction method and been investigated for their structural and electrocatalytic properties for the oxygen reduction reaction (ORR) in 0.5 M H2SO4 at 298 K. The study demonstrated that the bimetallic Pd-Co composite nanoparticles are, in fact, alloy nanoparticles with fcc crystalline structure. Partial substitution of Pd by Co (from 3.64 to 13.33 wt%) in 40 wt% Pd/graphene decreases the lattice parameter as well as the crystallite size and increases the apparent catalytic activity, the latter, however, being the greatest with 8 wt% Co. The ORR activity of the active 32 wt% Pd 8wt% Co is found to be considerably low when it was deposited on the support multiwall carbon nanotubes under similar conditions. The rotating disk electrode study indicated that the ORR on 32 wt% Pd 8 wt% Co/GNS in 0.5 M H2SO4 follows approximately the four-electron pathway.