The current study presents research into the effect of graphene oxide (GO) with a carbon to oxygen ratio of 4:1 on the fluidity, hydration, microstructure, mechanical and physical properties of Portland cement pastes and mortars. The amounts of GO investigated were 0.02%, 0.04%, and 0.06% by weight of cement, while for mortars, an extra composition with 0.1% was also prepared. According to the results, the fluidity of cement paste and mortar increased and the hydration process was slightly retarded with the addition of GO. Despite this, improvements in compressive and flexural strength were established in the mortars containing GO. The maximum effects (~22% and ~6%, respectively) were obtained with the addition of 0.06% GO. The calculation of estimated strength proportional to samples of equal density showed that for mortars cured for 7 days the gain in strength was directly related to the gain in density. For mortar samples cured for 28 days, the estimated strength was found to be significantly higher than that of the reference sample, indicating that besides density there are other factors determining the improvement in strength of mortars modified with GO. The possible structure strengthening mechanisms are discussed.