The effect of graphene nanosheet (GNS) reinforcement on the microstructure and mechanical properties of the titanium matrix composite has been discussed. For this purpose, composites with various GNS contents were prepared by cold pressing and sintering at various time periods. Density calculation by Archimedes’ principle revealed that Ti/GNSs composites with reasonable high density (more than 99.5% of theoretical density) were produced after sintering for 5 h. Microstructural analysis by X-ray diffraction (XRD) and a field emission scanning electron microscope (FESEM) showed that TiC particles were formed in the matrix during the sintering process as a result of a titanium reaction with carbon. Higher GNS content as well as sintering time resulted in an increase in TiC particle size and volume fraction. Microhardness and shear punch tests demonstrated considerable improvement of the specimens’ mechanical properties with the increment of sintering time and GNS content up to 1 wt. %. The microhardness and shear strength of 1 wt. % GNS composites were enhanced from 316 HV and 610 MPa to 613 HV and 754 MPa, respectively, when composites sintered for 5 h. It is worth mentioning that the formation of the agglomerates of unreacted GNSs in 1.5 wt. % GNS composites resulted in a dramatic decrease in mechanical properties.