Hydrogen storage using physisorption requires higher desorption temperatures than those possible using conventional adsorbents such as carbon. Using computational design, we predict that several materials have extremely strong physisorption interactions with hydrogen, including 12 kJ/mol heat of adsorption for hydrogen on some sites. Experimental adsorption isotherms on one of the materials, boron oxide, confirm the calculations, and large coverage is observed at temperatures as high as the boiling point of methane, 115 K. Since these materials have sp2-like bonding, they should be amenable to the rich variety of chemical manipulations that have been used with carbon.