Characterization of hydrogen bonds in CH4-(H2O)12 clusters was carried out by using several quantum chemistry tools. An initial stochastic search provided around 2 500 000 candidate structures, then, using a convex-hull polygon criterion followed by gradient based optimization under the Kohn-Sham scheme, a total of 54 well defined local minima were located in the Potential Energy Surface. These structures were further analyzed through second-order many-body perturbation theory with an extended basis set at the MP2/6-311++G(d,p) level. Our analysis of Gibbs energies at several temperatures clearly suggests a structural preference toward compact water clusters interacting with the external methane molecule, instead of the more commonly known clathrate-like structures. This study shows that CH4-(H2O)12 clusters may be detected at temperatures up to 179 K, this finding provides strong support to a recently postulated hypothesis that suggests that methane-water clusters could be present in Mars at these conditions. Interestingly, we found that water to water hydrogen bonding is strengthened in the mixed clusters when compared to the isolated water dimer, which in turn leads to a weakening of the methane to water hydrogen bonding when compared to the CH4-(H2O) dimer. Finally, our evidence places a stern warning about the abilities of popular geometrical criteria to determine the existence of hydrogen bonds.