The hydrogen economy is an envisaged system proposed for a sustainable energy future that comprises hydrogen production, storage, transportation, and stationary/mobile applications. Recently, research efforts are devoted to build a H2 economy; however, the reduced hydrogen volumetric density hinders the effective hydrogen storage. To combat this, material-based hydrogen storage is an emerging trend that has the potential to meet the ongoing goals of the United States Department of Energy. Herein, a critical review is presented on the state-of-the-art material-based hydrogen storage where nanostructured engineering and nanotechnology have driven a rapid growth in material design from physical sorbents (carbons, metal-organic frameworks, and organic polymer frameworks) to chemical sorbents (complex and metal nanohydrides). The research trends in physical sorption include tailoring the textural features of porous materials and enhancing the binding energy strength by inducing hydrogen spill-over effect and functionalization of surfaces. For chemical hydrogen storage, strategies are presented to ameliorate the sorption kinetics and thermodynamics using reactive hydrides, lightweight composites, and nanoconfinement of hydrides. Considering the long-term hydrogen storage, the concept of para hydrogen storage is also highlighted. Finally, the challenges and their plausible solutions are discussed to attain a sustainable hydrogen economy, in the near future.