Porous activated carbon or nanostructured carbon materials have a promising future as hydrogen storage media. The hydrogen storage capacity of nanostructured carbon materials can be further enhanced by spillover of atomic hydrogen from a supported catalyst. In the present work, both of these factors have been put to test to study the hydrogen storage capacity of palladium (Pd) nanoparticles dispersed over the surface of functionalized hydrogen-exfoliated- graphene (Pd/f-HEG). The high-pressure hydrogen storage measurements of HEG and Pd/f-HEG show a hydrogen storage capacity of 0.5 and 1.76 wt % respectively at 25 °C and 2 MPa pressure. Functionalization of graphene facilitates uniform dispersion of Pd nanoparticles, which result in an increased hydrogen storage capacity of graphene by 69%. Heats of adsorption have been calculated for HEG and Pd/f-HEG that are consistent with the theoretical calculations from literature and provide an experimental evidence for the spillover effect. © 2011 American Chemical Society.