Vertical van der Waals (vdW) heterostructures have shown potential for gas sensing owing to their remarkable sensitivity. However, the optimization process for achieving the best gas sensing performance is complicated by the heterostructure's reliance on both physical and electrical characteristics. This study employs density functional theory (DFT) to analyse the structural and electronic parameters of a MoTe2/InN vdW heterostructure. The findings of this study indicate that the vdW heterostructure has a type-II band alignment with higher adsorption energy towards NH3, NO2, and SO2 than the individual monolayers. In specific, the heterostructure is well suited for NO2 detection but has limitations in reliably detecting NH3 and SO2 due to longer recovery times. We find significant hybridization between the adsorbate and interacting surfaces' orbitals and a notable presence of NO2 molecular orbitals in proximity to the Fermi level. Additionally, dielectric and work function modulations offer a viable means to develop optical-based gas sensors that can selectively detect NO2. Our research provides valuable insights into vdW heterostructure design for high-performance gas sensors.