Graphene-based sensors exhibit high sensitivity, fast response, and good selectivity towards toxic gases but have low mechanical stability. The combination of graphene and two-dimensional hexagonal boron nitride (h-BN) is expected to increase the mechanical stability and enhance the adsorption performance of these gas sensors. Using first-principles calculations, we demonstrate that two-dimensional graphene/h-BN double layers can be used as good substrates for gas sensors with a small lattice mismatch of only 1.78%. Moreover, the presence of a h-BN layer widens the band gap by about 38 meV and considerably increases the work function, thus positively affecting the gas adsorption performance. Although these graphene/h-BN heterostructures do not change the physical adsorption mechanism of these sensors concerning the graphene-based materials, these bilayers significantly enhance the sensitivity of these sensors for detecting CO2, CO, NO, and NO2 toxic gases. Particularly, compared to the pristine graphene-based materials, the gas adsorption energies of graphene/h-BN increased by up to 13.78% for the adsorption of NO, and the shortest distances between the graphene/h-BN substrates and adsorbed gas molecules decreased. We also show that the graphene/h-BN heterostructure is more selective towards NOx gases while more inert towards COx gases, based on the different amounts of charge transferred from the substrate to the adsorbed gas molecules. Using the non-equilibrium Green functions in the context of density functional theory, we quantitatively associated these charge transfers with the reduction of the current passing through these scattering regions. These results demonstrate that graphene/h-BN heterostructures can be exploited as highly sensitive and selective roomtemperature gas sensors for detecting toxic gases.