With the increased efforts in finding new energy storage systems for mobile and stationary applications, an intensively studied fuel molecule is dihydrogen owing to its energy content, and the possibility to store it in the form of hydridic and protic hydrogen, for example, in liquid organic hydrogen carriers. Here we show that water in the presence of paraformaldehyde or formaldehyde is suitable for molecular hydrogen storage, as these molecules form stable methanediol, which can be easily and selectively dehydrogenated forming hydrogen and carbon dioxide. In this system, both molecules are hydrogen sources, yielding a theoretical weight efficiency of 8.4% assuming one equivalent of water and one equivalent of formaldehyde. Thus it is potentially higher than formic acid (4.4 wt%), as even when technical aqueous formaldehyde (37 wt%) is used, the diluted methanediol solution has an efficiency of 5.0 wt%. The hydrogen can be efficiently generated in the presence of air using a ruthenium catalyst at low temperature.