Fe-based catalysts doped with Mo were prepared and tested in the catalytic decomposition of methane (CDM), which aims for the co-production of CO2-free hydrogen and carbon filaments (CFs). Catalysts performance were tested in a thermobalance operating either at isothermal or temperature programmed mode by monitoring the weight changes with time or temperature, respectively, as a result of CF growth on the metal particles. Maximum performance of Fe–Mo catalysts was found at the temperature range of 700–900 °C. The addition of Mo as dopant resulted in an increase in the rate and amount of deposited carbon, reaching an optimum in the range 1.7–5.1% (mol) of Mo for Fe–Mo/Al2O3 catalysts, whereas for Fe–Mo/MgO catalyst an optimum at 5.1% Mo loading was obtained. XRD study revealed the effect of the Mo addition on the Fe2O3/Fe crystal domain size in the fresh and reduced catalysts. Tubular carbon nanostructures with high structural order were obtained using Fe–Mo catalysts, mainly as multiwall carbon nanotubes (MWCNTs) and bamboo carbon nanotubes. Fe–Mo catalysts showing best results in thermobalance were tested in a rotary bed reactor leading to high conversions of methane (70%) and formation of MWCNTs (5.3 g/h).