For conventional titanium matrix composites (TiMCs), there is always a trade-off issue between enhanced strength and ductility of these materials. In this study, we explore a new design methodology by reinforcing titanium alloy matrix with carbonaceous nanomaterials and investigate the mechanisms for achieving a good balance of their strength and ductility. The TiMCs were synthesized through a low-cost powder metallurgy route using pre-mixed Ti-6Al-4V (TC4) powders and various carbon based nanofillers, including graphite powders (GPs), graphene oxide nanosheets (GONs) and graphene nanoplates (GNPs), and were further rolled at a temperature of 1173 K with a deformation of 66.7%. Among these three types of carbon reinforcing sources, the GNPs are more easily reacted with TC4 matrix and form more contents of TiC phases after sintering owing to their larger amounts of defects than those of the GPs and GONs. TiC products are identified to play a bridging role for not only connecting the TC4 matrix but also forming coherent interfaces with the TC4 matrix, thus facilitating a strong interfacial bonding of the composites. The as-rolled GNPs/TC4 composites exhibit a 0.2% yield strength of 1146.36 MPa (with an elongation of ∼8.1%), which is 24.6%, 9.22% and 5.62% higher than those of pure TC4, GPs/TC4 and GONs/TC4 composites. The GNPs/TC4 nanocomposites show a better balance of strength and ductility than those of the other two types of nanocomposites. The synergetic strengthening mechanisms are identified to be Orowan strengthening effect, effective load transfer capability of GNPs, and in-situ formation of interfacial TiC structures, which provide optimum interfacial microstructures to achieve good mechanical properties of the TiMCs.