Among many solid state materials for hydrogen storage, magnesium hydride (MgH2) combines a hydrogen capacity of 7.6 wt % with the benefit of the low cost of production and abundance. The main difficulties for implementing MgH2 are slow absorption/desorption kinetics and high reactivity towards air and oxygen, which are also common issues in most lightweight metal hydrides. Previously, improvements in hydrogen storage and release properties have been reported by using nanostructured magnesium that can be obtained through various fabrication methods including ball-milling, mechanical alloying, and vapor transport. In this study, we investigate the hydrogen absorption and desorption properties of magnesium “nanotrees” fabricated by glancing angle deposition (GLAD) technique, and also conventional Mg thin films deposited at normal incidence. Mg nanotrees are about 15 µm long, 10 µm wide, and incorporate “nanoleaves” of about 20 nm in thickness and 1,2 µm in lateral width. A quartz crystal microbalance (QCM) gas absorption/desorption measurement system has been used for our hydrogen storage studies. Nanostructured and thin film Mg have been deposited directly on the surface of the gold coated unpolished quartz crystal samples. QCM hydrogen storage experiments have been performed at temperatures ranging between 100-300oC, and at H2 pressures of 10 and 30 bars. QCM measurements revealed that Mg nanotrees have better storage characteristics compared to Mg thin films. They can reach hydrogen storage values of about 4.80 wt% at 100oC, and up to about 6.71 wt% (which is close to the theoretical maximum storage value of Mg) at temperatures lower than 150oC. The significant enhancement in hydrogen absorption properties of Mg nanotrees is believed to originate from novel physical properties of their nanoleaves. These structures are very thin (~20 nm) and both surfaces are exposed to hydrogen enhancing the diffusion of hydrogen together with a decreased diffusion length. In addition, nanostructured Mg have been observed to be quite resistant to surface oxidation, which is believed to be due to the single crystal property of the Mg nanoleaves.