Bimetallic nanostructures (NSs) show enhanced electrocatalytic activity than their monometallic counterparts due to the synergetic effect. Here, we developed a strategy for the production of monometallic Pd and bimetallic AuPd, and their graphene composite. Thorough characterizations have been carried out to look deep into the surface morphology of the as-prepared NSs and their graphene counterparts. The electrocatalytic performance of the NSs was studied towards oxygen reduction reaction (ORR). The electronic properties of as-synthesized graphene supported monometallic, and bimetallic Nanostructures have been presented using Density Functional Theory simulations and support synergic effect due to hybridization between d orbital of Au, Pd, and 2p orbital of C. The enhanced density of states near Fermi level for the hybrid structure along with the charge transfer from metal d orbital to C 2p orbital may be responsible for increased conductivity. The graphene supported AuPd bimetallic NSs exhibited superior electrocatalytic performance towards ORR. The computed overpotential for ORR matches nicely with the experimental data. The interesting performance is attributed to the unique structure, proper dispersion of nanostructures on graphene support, and the synergetic effect of Au on Pd lattice.