The increasing consumption of Portland cement and natural aggregates is depleting natural resources and increasing environmental impact, particularly carbon dioxide emissions from cement manufacturing. This research aims to promote environmental sustainability by reusing construction waste and conserving natural resources for future generations. Limestone dust was used as a partial substitute for cement and granite waste as a partial substitute for fine aggregate in cement mortar. Seven mixes were cast in this study in addition to the reference mix. In the first three mixes, Portland cement was replaced at three weight ratios (5, 10, and 15%) with limestone dust, and the optimum mix was extracted. The other four mixes replaced the fine aggregate of the optimum mix of the three above with recycled granite waste at replacement ratios of 10, 30, 50, and 70% by weight. To demonstrate the effect of these materials on the cement mortar, the consistency (flow), compressive strength, tensile strength, flexural strength, and absorption were tested. The results obtained from this work demonstrated the possibility of obtaining a sustainable and environmentally friendly cement mortar made from replacing 10% of the weight of Portland cement with limestone dust and 50% of the weight of natural fine aggregate with recycled granite waste.