We investigate the potential for hydrogen storage of a new class of nanomaterials, metal-diboride nanotubes. These materials have the merits of a high density of binding sites on the tubular surfaces without the adverse effects of metal clustering. Using the TiB2 (8,0) and (5,5) nanotubes as prototype examples, we show through first-principles calculations that each Ti atom can host two intact H2 units, leading to a retrievable hydrogen storage capacity of 5.5 wt %. Most strikingly, the binding energies fall in the desirable range of 0.2-0.6 eV per H2 molecule, endowing these structures with the potential for room-temperature, near-ambient-pressure applications.