Poor ductility of titanium matrix composites with medium/high-strength reinforced with carbonaceous nanomaterials (eg., graphene, carbon nanotubes etc.), has seriously restricted their wide-range engineering and practical industry utility. Herein, we propose a new methodology to significantly and simultaneously enhance both ductility and tensile strength of the titanium matrix composites. We ball milled Ti-6Al-4V (TC4) powders with in-situ chemically synthetized Ni decorated multi-walled carbon nanotubes (i.e MWCNTs@Ni), and then sintered the composites powders using spark plasma sintering (SPS). We achieved both a significant balanced between superior strength and increased ductility of the composite using the MWCNTs@Ni nanopowders. The enhanced strength in composites is mainly attributed to the interfacial structures for effectively enhanced load transfer capability between MWCNTs@Ni and Ti matrix, e.g., the formation of coherent/semi-coherent interfaces among interfacial phases Ti2Ni, TiC and Ti matrix. Furthermore, we applied the dislocation theory to reveal the toughening mechanisms of MWCNTs@Ni in the MWCNTs@Ni/TC4 composites. This study provides a new methodology of fabricating metal matrix composites (reinforced with carbon based nanomaterial) with both high strength and good ductility.