Al1.8Fe0.2O3 solid solutions have been prepared as amorphous, η (cubic) and α (corundum) phases. The oxides have been reduced in a H2–CH4 gas mixture at 900 or 1000 °C, giving rise to composite powders containing alumina, α- and γ-Fe, Fe3C and different forms of carbon including nanotubes, thick tubes and spheroidal particles. The powders have been investigated using a combination of chemical analysis, X-ray diffraction, Mössbauer spectroscopy, scanning and transmission electron microscopy, thermogravimetric analysis and specific surface area measurements. Using the stable form (corundum) of Al1.8Fe0.2O3 as starting material favours the formation of carbon nanotubes compared to the other forms of carbon. This could partly result from the fact that the metal nanoparticles formed upon reduction of the α solid solution, which act as a catalyst for CH4 decomposition and possibly nanotube nucleation, are smaller than when using amorphous or η solid solutions. Moreover, the crystallization of these latter compounds during the reduction in some way provokes the entrapment of carbon within the oxide grains. The nanotubes, most of which are less than 10 nm in diameter, are arranged in bundles several tens of micrometers long.