We report a first-principles study of hydrogen storage media consisting of calcium atoms and graphene-based nanostructures. We find that Ca atoms prefer to be individually adsorbed on the zigzag edge of graphene with a Ca−Ca distance of 10 Å without clustering of the Ca atoms, and up to six H2 molecules can bind to a Ca atom with a binding energy of 0.2 eV/H2. A Ca-decorated zigzag graphene nanoribbon (ZGNR) can reach the gravimetric capacity of 5 wt % hydrogen. We also consider various edge geometries of the graphene for Ca dispersion.