Developing an efficient and affordable hydrogen-storage technology for on-board vehicular applications is a grand challenge to the success of a hydrogen economy. This challenge provides great opportunities for nanoscience and nanoengineering. Novel synthesis and characterization methods allow for an unprecedented degree of manipulation and tracking of the atomic structure in nanoassemblies. Furthermore, computational tools based on density functional theory, which combine fundamental predictive power with atomic resolution, provide a complementary and powerful means for the study and characterization of existing materials and prediction of new compounds and structural motifs, including those for hydrogen storage. In this chapter, we review the development of density functional theory-based computational studies of nanostructure design for hydrogen storage. Our emphasis is on complex metal hydrides. We also discuss the new developments in high surface area materials, including carbon-based materials, and metal- and covalent organic framework-based materials.