A facile and green approach has been developed for the in situ synthesis of hybrid nanomaterials based on dendrite-shaped Pd nanostructures supported on graphene (RG). The as-synthesized hybrid nanomaterials (RG-PdnDs) have been thoroughly characterized by high resolution transmission electron microscopy, X-ray photoelectron spectroscopy, atomic force microscopy, Raman spectroscopy and electrochemical techniques. The mechanism of formation of such dendrite-shaped Pd nanostructures on the graphene support has been elucidated using transmission electron microscopy (TEM) measurements. The RG induces the formation of, and plays a decisive role in shaping, the dendrite morphology of Pd nanostructures on its surface. Cyclic voltammetry and chronoamperometry techniques have been employed to evaluate the electrochemical performance of RG-PdnDs towards oxidation of methanol. The electrochemical (EC) activities of RG-PdnDs are compared with graphene-supported spherical-shaped Pd nanostructures, Pd nanodendrites alone and a commercial available Pd/C counterpart. The combined effect of the graphene support and the dendrite morphology of RG-PdnDs triggers the high electrocatalytic activity and results in robust tolerance to CO poisoning.