In this report, the fabrication of a novel SnO2-SnO nanostructure with p-n heterojunctions has been achieved through a facile one-pot and low-cost hydrothermal process. The structure and properties of the nanocomposite were analyzed with X-ray techniques and electron microscopy. HRTEM characterization showed that the p-n heterojunctions were formed with small n-type SnO2 nanocrystals dispersed on the surface of large p-type SnO crystals. Compared to the single SnO2-based material, a gas sensor fabricated from the SnO2-SnO composite exhibited an enhanced sensing performance for NO2 gas detection, with a limit of detection and sensitivity of 0.1 ppm and 0.26 ppm(-1), respectively, at a relatively low operating temperature (50 °C). Moreover, the p-n heterojunctions exhibited high sensing selectivity for NO2. Such a high sensing sensitivity and a low operating temperature make the SnO2-SnO p-n nanomaterial a promising gas sensor for practical NO2 gas detection. The improved sensing response characteristics of the hybrid material could be attributed to the p-n junctions formed through the in situ growth of SnO2 nanocrystals on SnO nanoplates. The present study is helpful for the design of novel gas sensing materials and the development of NO2 gas sensors.