The present research investigated for the first time the combined effect of microcrystalline cellulose (MCC) and carbon nanotube (CNT) on the performance of cement composites. Multi-scale or hierarchical composites were developed by dispersing MCC and multi-wall CNT (MWCNT) within the cementitious matrix as reinforcements. Homogeneous suspensions of MCC (0.4 wt% and 1 wt%) and CNTs (0.2 wt% and 0.6 wt%) in water were prepared using two different surfactants, cetyltrimethylammoniumbromide (CTAB) and Pluronic F-127 using ultrasonication energy, and the suspensions were subsequently added to cement-sand mixture to fabricate cementitious composites. The composite samples were stored in water for 28 and 56 days to carry out the hydration process and were next characterized for flexural and compressive properties, dry bulk density, porosity, hydration products and fracture surface morphology. It was observed that the flexural and compressive strengths of cement composites improved significantly due to the MCC - CNT hybrid reinforcement. The highest improvements in flexural strength of 12.3% and 23.2% and compressive strength of 16.3% and 27.9% were achieved with 0.5 wt % MCC-0.3 wt % CNT in 28 and 56 days, respectively. In addition, significant improvements in flexural modulus, flexural strain and fracture energy were also noticed. Positive influence of hybrid reinforcement on the porosity of cementitious composites was also confirmed; the average pore diameter of plain mortar reduced from 47.5 nm to 30 nm. Further, the multi-scale composites exhibited higher bulk density, better hydration and crack bridging by CNTs leading to higher fracture energy.