In this work we use density functional theory (DFT) calculations to benchmark empirical potentials for the interaction between nickel and sp2 bonded carbon nanoparticles. These potentials are then used in order to investigate how Ni decorated or coated carbon nanotubes (CNT) affect the mechanical properties of Al/CNT composites. In particular we look at the pull-out behaviour of pristine as well as Ni-decorated and Ni-coated CNT from an Al matrix. Our result shows that Ni coating may produce an extended interface (“interphase”) where a significant amount of energy is dissipated during CNT pull-out, leading to a high pull-out force. We also demonstrate that surface decorated CNT may act as efficient nano-crystallization agents and thus provide a novel strengthening mechanism not previously discussed in the literature. We discuss our results in view of promising approaches for engineering CNT-metal interfaces such as to achieve high strength metal-CNT composites.