In this work, an ultrasensitive and low detection limit of toluene gas sensor based on SnO₂-decorated NiO nanostructure synthesized via a simple hydrothermal route was described. The test results demonstrated that the sensor based on SnO₂-decorated NiO nanostructure showed excellent sensitivity and selectivity toward toluene, giving a high response of 66.2-100 ppm, which was 50 times higher than that of the pure NiO nanospheres (1.3-100 ppm). Additionally, the sensor had surpassingly low detection limit (ppb-level), showing a response of 1.2-10 ppb toluene. Besides, the sensor also exhibited anti-humidity properties in some way, giving an acceptable response (11.1-10 ppm) to toluene at 90% relative humidity. The ultrasensitive characteristics and low detection limit could be explained from the variation of the carrier concentration caused by the change of the thickness of near-surface hole accumulation layer between p-type NiO and n-type SnO2. Furthermore, the increase of oxygen adsorption also improved the sensing performance.