We study polylithiated molecules as building blocks for hydrogen storage materials, using first-principles calculations. CLi₄ and OLi₂ 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 H₂. Bonding between Li and C or O is strongly polar and H₂ molecules attach to the partially charged Li atoms without dissociating, which is favorable for (de)hydrogenation kinetics. CLi_n and OLi_m 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 H₂.