Amorphous titanium dioxide-coated carbon nanotubes (CNTs) were prepared by atomic layer deposition (ALD) and investigated as sensing layers for resistive NO2 and O2 gas sensors. By varying ALD process conditions and CNT structure, heterostructures with different metal oxide grain size, morphology and coating thickness were synthesized. Higher responses were observed with homogeneous and continuous 5.5 nm thick films onto CNTs at an operating temperature of 150 °C, while CNTs decorated with either discontinuous film or TiO2 nanoparticles showed a weak response close to the one of device made of bare CNTs. An unexpected p-type behavior in presence of the target gas was also noticed, independently of the metal oxide morphology and thickness. Based on previous works, hypotheses were made in order to explain the p-type behavior of TiO2/CNT sensors.