The integration of waste materials in construction is increasingly recognized as a vital component of environmentally sustainable engineering practices. Among these materials, steel slag and recycled concrete aggregates stand out as promising alternatives to natural resources in mortar production. However, their potential as substitutes necessitates thorough characterization and assessment. In this study, both SS and RCFA were subjected to physical and chemical analyses to evaluate their suitability for mortar production. Laboratory experiments were conducted using RCFA from crushed concrete cubes and steel slag sourced from the steel factories to investigate their performance as partial replacements for natural sand in mortar mixes. Replacement levels (0%, 10%, 20%, 30%, 40%, and 50%) were considered, and cubes measuring 5 × 5 × 5 cm were prepared in a quantity of 384, the resulting mortars underwent a variety of tests including fresh, harden, and durability tests. The compressive strength of the mortars was monitored at various ages (3, 7, 28, and 56 days) to assess their long-term performance. Hence, the mortar with 0% replacement served as the control mix. The findings indicate that while the compressive strength generally decreases with higher replacement ratios of RCFA and SS, an optimum replacement ratio of 40% (20% SS and 20% RCFA) yielded the highest compressive strength.