Establishing heterostructures, as a good strategy to improve gas sensing performance, has been studied extensively. In this research, In2O3-composite SnO2 nanorod (ICTOs) heterostructures have been prepared via electrospinning, followed by calcination. It is found that In2O3 can improve the carrier density and oxygen deficiency of SnO2. In particular, the 3ICTO (Sn : In atom ratio of 25 : 0.3) nanorods with special particle distributions show an excellent sensing response towards different concentrations of NOx at room temperature. The highest sensing response is up to 8.98 for 100 ppm NOx with a fast response time of 4.67 s, which is over 11 times higher than that of pristine SnO2 nanorods at room temperature and the lowest detection limit is down to 0.1 ppm. More significantly, it presents good stability after 30 days for NOx of low concentration (0.1 ppm and 0.5 ppm). In addition, the rational band structure model combined with the surface depletion model which describe the NOx gas sensing mechanism of 3ICTO are presented. The 3ICTO nanorods may be promising in the application of gas sensors.