The combination of carbon nanotubes with transition metal oxides can exhibit complementary charge storage properties for use as electrode materials for next generation energy storage devices. One of the biggest challenges so far is to synthesize homogeneous oxide coatings on carbon nanotube structures preserving their integrity. Here we present the formation of conformal coatings of Fe2O3 on vertically aligned carbon nanotubes obtained by atomic layer deposition. We investigate the effect of pristine, nitrogen plasma and water plasma treated carbon nanotube surfaces on the ALD-growth of Fe2O3 using ferrocene and ozone precursors. The surface morphology, coating thickness, microstructure and surface chemistry of iron oxide-carbon nanotube composites and their ultimate influence on the electrochemical behavior of the composites are evaluated. The most effective surface functionalization is that achieved by H2O plasma treatment, whereas untreated carbon nanotubes, despite the lack of active sites in the starting pristine surface, can be coated with an inhomogeneous Fe2O3 film.