In this paper, we report high pressure experimental measurements and detailed density functional theory (DFT) as well as molecular dynamic (MD) simulations of methane (CH4) solubility in natural deep eutectic solvents (NADESs) that were prepared by using alanine (Al), betaine (Be), and choline chloride (ChCl) used as hydrogen bond acceptors (HBA) and lactic acid (La), malic acid (Ma), and phenylacetic acid (Paa) used as hydrogen bond donors (HBD). Experiments were performed on Al:La, Be:La, ChCI:La, ChCI:Ma, and ChCI:Paa systems up to 50 bar at 298.15 K. Meanwhile, this work includes the quantum theory of atoms in molecules (QTAIM) calculations that allow quantifying and characterizing the short-range interactions of studied systems, which is reported for the first time for NADESs and CH4 interactions. Furthermore, MD simulations shed light onto the characteristics of intermolecular forces, particularly for hydrogen bonding, molecular arrangements in the liquid phases, and their role in fluid's properties. The presented results showed that the studied NADESs can be used for selective CO2/CH4 separation in gas processing applications.