Waste tires have recently emerged as one of the world's most vital environmental challenges. Crumb rubber made from recycled tires can be utilized to replace a portion of the fine aggregate in cement mortar. This encourages the construction industry's long-term development. Reducing natural resource use could benefit the economy and the environment. This study explores the effect of the inclusion of 0.1% Edge-Oxidized Graphene Oxide (EOGO), by weight of cement, in improving the performance of cement mortars containing 6% and 12% of different sizes of crumb rubber. Cube molds were utilized to evaluate compressive strength, flexural strength, and porosity after 28 days of curing time. The variables considered in this study included the rubber sizes (0–1.0 mm, 1.0–4.0 mm), the rubber content (6%, 12%), and the inclusion of 0.1% EOGO. Results showed an enhancement of the mechanical properties of cement mortar by the inclusion of EOGO in mortar mixes. Results show that incorporating 0.1% of graphene oxide could improve the compressive strength compared with the reference mix by an average of 12% and 8% at 7- and 28-day curing age, respectively. For the flexural strength, test results indicated that incorporating EOGO could improve the performance of cement mortars containing 6% crumb rubber by an average of 7% and at a 7-day curing age compared with the 6% rubber mortars without EOGO. Results demonstrated that the use of the fine sizes of rubber particles in mortar mixes gave higher performance compared with mixes with rubber particles with larger sizes. It can be seen from the result that the mortar mix with 0.1% EOGO and 6% rubber is the optimum mortar mix for a sand replacement among other mixes including the control mix. Therefore, crumb rubber is acceptable to be used as a sand replacement with the inclusion of EOGO.