One of the most vital problems in fuel cell research is the synthesis of low cost, active and stable electro-catalyst for anodic and cathodic reactions. In this work, palladium nanostructures with a coral-like morphology (PdNC) is deposited on reduced graphene oxide (rGO) by electrochemical method. The nanocoral exhibits superior activity towards methanol oxidation (MOR) and oxygen reduction reactions (ORR) in alkaline media. To improve the efficiency, Pt is deposited on the surface by galvanic replacement. Presence of Pt on palladium nanocoral (PdNC-Pt) leads to an enhanced catalytic activity for both the electrode reactions. A mass activity of 1700 mA mg− 1 at 1.04 V for MOR and a current density of −5.72 mA cm− 2 and an onset potential of 0.86 V vs RHE is observed for ORR. Both the electrode reactions result in higher current than the commercial Pd/C and Pt/C catalysts. A remarkable improvement in durability is seen for ORR after depositing Pt.