In metal matrix composites (MMCs), the interface between the metal matrix and reinforcements critically affects mechanical properties of MMCs because the load can transfer at the interface via the interfacial shear stress. Generally, MMCs reinforced with multi-walled carbon nanotubes (MWCNTs) can have the clear interfacial structure, without the formation of carbide. However, in titanium matrix composites (TMCs), carbon materials, including MWCNTs, have a large solubility of titanium, so the interfacial structure in the TMCs can be modified. High-energy ball milling, which is severely heavy, contributes to vary the solubility of carbon in the Ti matrix and develop an interstitial solid solution at the interface between the Ti matrix and MWCNTs. Therefore, it leads to significantly enhancing the strengthening efficiency of TMCs and achieves the superior yield strength of TMCs, ~2.1 GPa, with a small amount of MWCNTs (2 vol. %).