Titanium oxide nanoparticles were coated on multiwall carbon nanotubes (MWCNTs) using an atmospheric pressure chemical vapor deposition (CVD) to achieve highly compact nanoparticles of about 5 nm on CNT structure. The CNTs with a diameter of about 50 nm were grown by plasma enhanced CVD. Gas sensitivity of the fabricated structure was investigated and compared with TiO2/CNT composite-based gas sensors. The effect of the structural interaction between the nanoparticles and the CNT wall on sensing mechanism of the as-prepared gas sensors was investigated. Ultrasensitive gas sensors were obtained by TiO2/CNT nanostructures with strong interaction between the MWCNT and the TiO2 nanoparticles. The measurements show high chemical activity and exceptional electrical response of the as-prepared structure being exposed to gases. Scanning and transmission electron microscopy and X-ray diffraction analysis were used to obtain structural information.