The molecular structure of dense homogeneous fluid water-methane mixtures has been determined for the first time using high-pressure neutron-scattering techniques at 1.7 and 2.2 GPa. A mixed state with a fully H-bonded water network is revealed. The hydration shell of the methane molecules is, however, revealed to be pressure-dependent with an increase in the water coordination between 1.7 and 2.2 GPa. In parallel, ab initio molecular dynamics simulations have been performed to provide insight into the microscopic mechanisms associated with the phenomenon of mixing. These calculations reproduce the observed phase change from phase separation to mixing with increasing pressure. The calculations also reproduce the experimentally observed structural properties. Unexpectedly, the simulations show mixing is accompanied by a subtle enhancement of the polarization of methane. Our results highlight the key role played by fine electronic effects on miscibility and the need to readjust our fundamental understanding of hydrophobicity to account for these.