Two-dimensional (2D) materials have gained considerable attention in chemical sensing owing to their naturally high surface-to-volume ratio. However, the poor response time and incomplete recovery restrict their application in practical, high performance gas sensors. In this work, we fabricated air-stable ReS₂/GaSe heterostructure-based NO₂ gas sensors with excellent gas sensing response, recovery, selectivity and a low limit of detection (LOD) toward nitrogen dioxide (NO₂). The ReS₂/GaSe heterostructure was prepared via mechanical exfoliation and an all-dry transfer method. Before the sensing measurements, temperature-dependant transport measurements were carried out. The Schottky Barrier Height (SBH) of the ReS₂/GaSe heterostructure was calculated and the corresponding transport mechanisms were discussed. The fabricated gas sensors showed a significant response enhancement with full reversibility toward ppm-level NO₂ (response of ∼17% at 3 ppm, a LOD of ∼556 ppb) at an operating temperature of (33 °C). In particular, the total response and recovery time of the ReS₂/GaSe was revealed to be less than 4 min (∼38 s and ∼174 s, respectively) for the 250 ppm concentration, which is one of the best response and recovery time toward ppm-level NO₂. The excellent sensing performances and recovery characteristics of the ReS₂/GaSe structure are attributed to its efficient charge separation, unique interlayer coupling and desirable band alignments. This atomically thin, ultrasensitive gas sensor that operates at room temperature is a strong technological contender to conventional metal oxide gas sensors, which often require elevated temperatures.