Establishing heterostructures is a good strategy to improve gas sensing performance, and has been studied extensively. In this work, mesoporous InN/In2O3 composite (InNOCs) heterostructures were prepared through a simple two-step strategy involving hydrothermal synthesis of In2O3 and subsequent nitriding into InN-composite In2O3 heterostructures. We found that the InN content has great influence on the resistance of InNOCs, and thus, the gas sensing performance. In particular, InNOC-36.9 (with InN content of 36.9% in the composites) shows an excellent sensing response towards different concentrations of NO2, as well as good stability after one week of exposure to 200 ppb NO2 at room temperature. The highest sensing response (ΔR/R0 ) is up to 1.8 for the low NO2 concentration of 5 ppb. Even more significantly, the theoretical limit of detection (LOD) of the InNOC-36.9 sensor is 31.7 ppt based on a signal-to-noise ratio of 3 (the measured LOD is 5 ppb), which is far below the US NAAQS value (NO2: 53 ppb). In addition, a rational band structure model combined with a surface reaction model is proposed to explain the sensing mechanism.