This chapter focuses on the remarkable mechanical enhancement of cementitious composites reinforced with graphene oxide (GO). GO incorporation in cement-based composites leads to superior mechanical attributes including compressive strength, flexural strength, tensile strength, fracture and toughness properties. The enhanced properties of the resulting composites are attributed to excellent GO properties leading to improved crack bridging, interfacial strengthening, and strain hardening. However, a major issue regarding uniform GO dispersion in alkaline cementitious solution is high susceptibility of its agglomeration due to which its beneficial effects may be hampered. In order to effectively disperse GO in cementitious composites, various techniques such as steric stabilization and electrodeposition of GO or addition of a suitable material along with GO (e.g. silica fume) which have been discussed at length as well. Further, prospects and challenges for its future applications in construction and building materials as well as modeling approaches for GO incorporated cementitious composites have also been covered.