Excellent mechanical, thermal, and electrical properties of carbon nanotubes (CNTs) and nanofibers (CNFs) have motivated the development of advanced nanocomposites with outstanding and multifunctional properties. After achieving a considerable success in utilizing these unique materials in various polymeric matrices, recently tremendous interest is also being noticed on developing CNT and CNF reinforced cement-based composites. However, the problems related to nanomaterial dispersion also exist in case of cementitious composites, impairing successful transfer of nanomaterials' properties into the composites. Performance of cementitious composites also depends on their microstructure which is again strongly influenced by the presence of nanomaterials. In this context, the present paper reports a critical review of recent literature on the various strategies for dispersing CNTs and CNFs within cementitious matrices and the microstructure and mechanical properties of resulting nanocomposites.