A novel tubular NiO nanostructure was synthesized by a facile and low-cost hydrothermal strategy and then further functionalized by decorating α-Fe2O3 nanorods. The images of electron microscopy indicated that the α-Fe2O3 nanorods were assembled epitaxially on the surfaces of NiO nanotubes to form α-Fe2O3/NiO nanotubes. As a proof-of-concept demonstration of the function, gas sensing devices were fabricated from as-prepared α-Fe2O3/NiO nanotubes, and showed enhanced gas response and excellent selectivity toward toluene, giving a response of 8.8 to 5 ppm target gas, which was about 7.8 times higher than that of pure NiO nanotubes at 275 °C. The improved gas sensing performance of α-Fe2O3/NiO nanotubes could be attributed to the unique tubular morphology features, p-n heterojunctions and the synergetic behavior of α-Fe2O3 and NiO.