A novel hierarchical heterostructure of alpha-Fe2O3 nanorods/TiO2 nanofibers with branch-like nanostructures was fabricated using a simple two-step process called the electrospinning technique and hydrothermal process. A high density of alpha-Fe2O3 nanorods (about 200 nm in diameter) was uniformly deposited on a TiO2 nanofibers backbone. The phase purity, morphology, and structure of hierarchical heterostructures are investigated by X-ray diffraction (XRD), field emission scanning electron microscopy (FESEM), transmission electron microscopy (TEM), and energy-dispersive X-ray (EDX) analysis. The highly branched alpha-Fe2O3/TiO2 heterostructures provided an extremely porous matrix and high specific surface area required for high-performance gas sensors. Different nanostructured alpha-Fe2O3/TiO2 heterostructures are also investigated by controlling the volume ratio of the reactants. The alpha-Fe2O3/TiO2 heterostructures with a proper mixture ratio of the reactants sensor exhibit obviously enhanced sensing characteristics, including higher sensing response, lower operating temperature, faster response speed, and better selectivity in comparison with other ones. Moreover, the alpha-Fe2O3/TiO2 heterostructures sensor also exhibits excellent sensing performances compared with alpha-Fe2O3 nanorods and TiO2 nanofibers sensors. Thus, the combination of TiO2 nanofibers backbone and alpha-Fe2O3 nanorods uniformly decorated endows a fascinating sensing performance as a novel sensing material with high response and rapid responding and recovering speed.