In recent years, nano-reinforcing technologies for cementitious materials have attracted considerable interest as a viable solution for compensating the poor cracking resistance of these materials. In this study, for the first time, titanium nanotubes (TNTs) were incorporated in cement pastes and their effect on the mechanical properties, microstructure, and early-age hydration kinetics was investigated. Experimental results showed that both compressive (~12%) and flexural strength (~23%) were enhanced with the addition of 0.5 wt.% of TNTs relative to plain cement paste at 28 days of curing. Moreover, it was found that, while TNTs accelerated the hydration kinetics of the pure cement clinker phase (C3S) in the early age of the reaction (within 24 h), there was no significant effect from adding TNTs on the hydration of ordinary Portland cement. TNTs appeared to compress the microstructure by filling the cement paste pore of sizes ranging from 10 to 100 nm. Furthermore, it could be clearly observed that the TNTs bridged the microcracks of cement paste. These results suggested that TNTs could be a great potential candidate since nano-reinforcing agents complement the shortcomings of cementitious materials.