TiO2 with different morphology was deposited on acid-treated multi-walled carbon nanotubes (CNTs) by atomic layer deposition at 100 °C-300 °C to form a TiO2@CNT structure. The TiO2 fabricated at 100 °C was an amorphous film, but became crystalline anatase nanoparticles when fabricated at 200 °C and 300 °C. The saturation growth rates of TiO2 nanoparticles at 300 °C were about 1.5 and 0.4 Å/cycle for substrate-enhanced growth and linear growth processes, respectively. It was found that the rate constants for methylene blue degradation by the TiO2@CNT structure formed at 300 °C were more suitable to fit with second-order reaction. The size of 9 nm exhibited the best degradation efficiency, because of the high specific area and appropriate diffusion length for the electrons and holes.