Commercial energy storage has moved from the margins to the mainstream as it fosters flexibility in our smarter, increasingly integrated energy systems. Natural gas has been identified by many as the fuel to take us to the no-carbon horizon; where a hydrogen economy waits on development. These two actors are already connected in precursor applications as transitional solutions for hydrogen handling and transportation are sought ahead of a fully established hydrogen infrastructure. This monograph explores some of leading advances in methane and hydrogen storage as well as the interesting link between these two important elements in our evolving energy system mosaic. Topics covered include: hydrogen absorption for storage; power-to-gas for energy system integration and storage; methanation for power-to-gas applications; production of hydrogen from methane decarbonisation into power to gas scenarios; power-to-gas in an ancillary service market; methane in MOFs: where, why and how; thermal management as a key in storing adsorbed natural gas; and gas hydrate potential and development for methane storage.