This study presents the results of an experimental study on the mechanical properties of graphene oxide (GO)-cement mortar composites. Four different mixes of cement mortars with GO contents of 0%, as a control mix, 0.03, 0.1, and 0.5% by the weight of cement were prepared. The effect of the GO content on the axial tension and compression strength of mixes were examined. Scanning electron micrographs (SEM), X-ray diffraction (XRD), and Fourier transform infrared spectroscopy (FTIR) tests were performed on the specimens to understand the mechanisms behind the mechanical test results. The results show that the tensile and compressive strength of GO-cement mortar composites steadily increase up to 37.5 and 77.7% with an increase in GO content to 0.1%, respectively. This is attributed to the improved bonding between the cement matrix and GO particles due to the high dispersibility of GO sheets in the composite at the optimum concentration. The results also show that further increase in the GO content was unfavorable as the GO sheets restacked, which reduced the bridging stress and gave poor dispersion of GO in the composite.