A nanocomposite with Pd nanoparticles deposited on graphene is prepared through a facile and low cost approach. The Pd-graphene nanocomposite was easily synthesized using dip coating method on glassy carbon electrode (GCE). The resulting Pd-graphene nanocomposite was characterized by scanning electron microscopy (SEM) and energy dispersive spectroscopy (EDS). SEM indicates the formation of Pd nanoparticles with sizes in the range of 40–80 nm on graphene. Also, the behavior of as-prepared Pd-graphene nanocomposite as electrocatalyst for hydrogen evolution reaction (HER) was investigated by cyclic voltammetry in 0.5 M H2SO4. Pd-graphene nanocomposite shows an enhanced catalytic activity toward HER than Pd and graphene. These results demonstrate that graphene is an excellent support material for Pd nanoparticles. It was observed that the current density of Pd-graphene nanocomposite had a little decrease after continues 500 cycling, which shows the catalyst presents high stability in the recycling process. Furthermore, the chronoamperometric method confirmed that the fabricated catalyst has good stability for HER. The good catalytic activity suggests that the Pd-graphene nanocomposite can be a promising electrocatalyst in hydrogen production process.