Gas hydrates consist of hydrogen-bonded water frameworks enclosing guest gas molecules and have been the focus of intense research for almost 40 y, both for their fundamental role in the understanding of hydrophobic interactions and for gas storage and energy-related applications. The stable structure of methane hydrate above 2 GPa, where CH4 molecules are located within H2O or D2O channels, is referred to as methane hydrate III (MH-III). The stability limit of MH-III and the existence of a new high-pressure phase above 40 to 50 GPa, although recently conjectured, remain unsolved to date. We report evidence for a further high-pressure, room-temperature phase of the CH4-D2O hydrate, based on Raman spectroscopy in diamond anvil cell and ab initio molecular dynamics simulations including nuclear quantum effects. Our results reveal that a methane hydrate IV (MH-IV) structure, where the D2O network is isomorphic with ice Ih, forms at similar to 40 GPa and remains stable up to 150 GPa at least. Our proposed MH-IV structure is fully consistent with previous unresolved X-ray diffraction patterns at 55 GPa [T. Tanaka et al., J. Chem. Phys. 139, 104701 (2013)]. The MH-III -> MH-IV transition mechanism, as suggested by the simulations, is complex. The MH-IV structure, where methane molecules intercalate the tetrahedral network of hexagonal ice, represents the highest-pressure gas hydrate known up to now. Repulsive interactions between methane and water dominate at the very high pressure probed here and the tetrahedral topology outperforms other possible arrangements in terms of space filling.