Concrete is the most used construction material, driven by industrialization and urbanization, with worldwide demand surpassing 20 billion tons annually. Increasing demand for sustainable construction materials has led to research into the use of recycled concrete aggregates (RCA), palm oil fiber (POF), and coconut shell (CS) waste for sustainability advancement and improvement of mechanical performance. RCA was incorporated as a partial replacement of natural coarse aggregate at 2.5–10% by weight of the coarse aggregate fraction. The mixes demonstrated optimal workability and strength at the 2.5% RCA level. The addition of fibers improved mechanical properties at 2.5%; however, it decreased workability as the fiber content increased. CS waste presented a sustainable option but reduced workability and compressive strength in the high proportions due to higher porosity and a weak interfacial transition zone. These findings indicate the potential of these materials for sustainable concrete applications with proper optimization.