Methane is one of the simplest stable molecules that is both abundant and widely distributed across space. It is thought to have partial origin from interstellar molecular clouds, which are near the beginning of the star formation cycle. Observational surveys of CH$_4$ ice towards low- and high-mass young stellar objects showed that much of the CH$_4$ is expected to be formed by the hydrogenation of C on dust grains, and that CH$_4$ ice is strongly correlated with solid H$_2$O. Yet, this has not been investigated under controlled laboratory conditions, as carbon-atom chemistry of interstellar ice analogues has not been experimentally realized. In this study, we successfully demonstrate with a C-atom beam implemented in an ultrahigh vacuum apparatus the formation of CH$_4$ ice in two separate co-deposition experiments: C + H on a 10 K surface to mimic CH$_4$ formation right before H$_2$O ice is formed on the dust grain, and C + H + H$_2$O on a 10 K surface to mimic CH$_4$ formed simultaneously with H$_2$O ice. We confirm that CH$_4$ can be formed by the reaction of atomic C and H, and that the CH$_4$ formation rate is 2 times greater when CH$_4$ is formed within a H$_2$O-rich ice. This is in agreement with the observational finding that interstellar CH$_4$ and H$_2$O form together in the polar ice phase, i.e., when C- and H-atoms simultaneously accrete with O-atoms on dust grains. For the first time, the conditions that lead to interstellar CH$_4$ (and CD$_4$) ice formation are reported, and can be incorporated into astrochemical models to further constrain CH$_4$ chemistry in the interstellar medium and in other regions where CH$_4$ is inherited.
