We study polylithiated molecules as building blocks for hydrogen storage materials, using first-principles calculations. CLi4 and OLi2 bind 12 and 10 hydrogen molecules, respectively, with an average binding energy of 0.10 and 0.13 eV, leading to gravimetric densities of 37.8 and 40.3 wt % of H2. Bonding between Li and C or O is strongly polar and H2 molecules attach to the partially charged Li atoms without dissociating, which is favorable for (de)hydrogenation kinetics. CLin and OLim molecules can be chemically bonded to graphene sheets to hinder the aggregation of such molecules. In particular B- or Be-doped graphene strongly bind the molecules without seriously affecting the hydrogen binding energy. This still leads to a hydrogen storage capacity in the range of 5−8.5 wt % of H2.