Helium and methane are major components of giant icy planets and are abundant in the universe. However, helium is the most inert element in the periodic table and methane is one of the most hydrophobic molecules, thus whether they can react with each other is of fundamental importance. Here, our crystal structure searches and first-principles calculations predict that a He3CH4 compound is stable over a wide range of pressures from 55 to 155 GPa and a HeCH4 compound becomes stable around 105 GPa. As nice examples of pure van der Waals crystals, the insertion of helium atoms changes the original packing of pure methane molecules and also largely hinders the polymerization of methane at higher pressures. After analyzing the diffusive properties during the melting of He3CH4 at high pressure and high temperature, in addition to a plastic methane phase, we have discovered an unusual phase which exhibits coexistence of diffusive helium and plastic methane. In addition, the range of the diffusive behavior within the helium-methane phase diagram is found to be much narrower compared to that of previously predicted helium-water compounds. This may be due to the weaker van der Waals interactions between methane molecules compared to those in helium-water compounds, and that the helium-methane compound melts more easily.