In this work, first-principles total energy calculations were performed in order to study the structure and hydrogen storage behavior on Ca-decorated graphene. On the stable structure of Ca-decorated graphene with root 3 x root 3 - 30 degrees reconstruction, the first hydrogen molecule adsorbed is dissociative, with the energy barrier of only 0.05 eV. The electrons of H atoms saturate the electronic states of Ca around the Fermi level and enhance the system stability. Further adsorption of hydrogen molecules on Ca-adsorbed graphene is weak, which indicates Ca-adsorbed graphene does not suit for the hydrogen storage via physical adsorption of hydrogen molecules. On the other hand, hydrogen spillover mechanism could exist on Ca-decorated graphene. On the graphene with one Ca dimer adsorbed, one of the four H atoms adsorbed on the Ca dimer adsorbes chemically on C in graphene more stably by 0.37 eV than on the Ca dimer. With the number of hydrogen atoms adsorbed on Ca-decorated graphene increases, the binding energy of hydrogen atoms tends to increase. Thus, the spillover process is energetically favorable. The hydrogen storage capacity via the spillover mechanism in Ca-adsorbed graphene depends on the Ca content and could approach 7.7 wt.%. Copyright (C) 2012, Hydrogen Energy Publications, LLC. Published by Elsevier Ltd. All rights reserved.