Most of the previous research on the use of recycled materials for concrete examined only the effect of using recycled aggregate in concrete mixes. In this paper, the combined effects of recycled aggregate and recycled water on the strength and durability of recycled concrete are presented and discussed. Three types of mixing water were examined and found to comply with the requirements of EN 1008 and ASTM C94. The test program involved the preparation of a moderate strength concrete made out of recycled water and recycled aggregate obtained from demolition and construction wastes. In the demolition waste series, four mixes of concrete were prepared using different contents of aggregate extracted from demolition waste and recycled water. The effect of the recycled aggregate and recycled water on the axial and flexural strength was found to be moderate but had a significant negative impact on the durability. In the construction waste series, to enhance the durability and to lower the carbon footprint of the recycled concrete mix, the OPC was replaced by GGBS. Four replacement ratios, 60%, 70%, 80%, and 90%, of the OPC were examined. While all the four mixes achieved good strength and durability, the mix with 90% GGBS did not achieve the target strength of 40 MPa even after 56 days. In general, fully recycled concrete mix with 80% GGBS replacement is recommended for any sustainable future construction in the Gulf with an expected carbon footprint of 129.9 kg/m³.