We elucidate the mechanisms by which multi-walled carbon nanotubes (MWCNTs) influence the microstructure, fracture behavior, and hydration of cement paste. We disperse MWCNTs using a multi-step approach that involves high-energy pre-dispersion using ultrasonic energy followed by low-energy dispersion using un-hydrated cement particles. In turn, the low-energy dispersion step involves high-shear mixing and mechanical stirring. High-resolution environmental scanning electron microscopy of cement+0.2 wt% MWCNT, cement+0.5 wt% MWNCT, and of cement+1 wt% MWCNT show that MWCNTs bridge air voids, thereby refining the pore size and strengthening the C-S-H matrix. The fracture toughness increased by 9.38% with the addition of 0.2 wt% multi-walled carbon nanotubes, and by 14.06% with the addition of 0.5 wt% multi-walled carbon nanotubes and ligament bridging was the dominant toughening mechanism. Moreover, for all reinforcement levels, MWCNTs induced a conversion of low-density C-S-H into high-density C-S-H along with a drastic drop in the capillary porosity: adding 0.1-0.5 wt% MWCNT resulted in a 200% increase in the volume fraction of high-density C-S-H. Thus, our experiments show that MWCNT enhances the mechanical properties and transport properties by: (i) promoting high-density C-S-H formation, (ii) promoting calcium hydroxide formation, (iii) filling microscopic air voids, (iv) reducing the capillary porosity, (v) increasing the fraction of small gel pores (1.2-2 nm in size), and (vi) by bridging microcracks.