Concrete block masonry units (CBMUs) are the most commonly used building material in the construction industry. However, CBMUs are still produced from conventional materials like natural aggregates. Aggregate materials normally occupy about 70% of the CBMU volume. The excessive extraction of virgin aggregate depletes natural resources, destroys the habitats of many species, and affects the natural flow of streams in water bodies. At the same time, the amount of solid waste, including construction waste from the demolition of old buildings, continues to increase, leading to higher costs for disposing of these wastes in increasingly scarce landfill sites. One solution to address the growing solid waste challenge and to preserve natural aggregate resources from depletion is the adoption of large-scale recycling of glass, plastic, rubber, construction and demolition, and other solid wastes into aggregate that can be used in the production of CBMUs. This study presents a critical review of the latest research on using recycled aggregates in CBMU manufacturing. The physical, mechanical, and durability properties of CBMUs that incorporated recycled aggregates were extensively analyzed, and concluding remarks and practical recommendations were drawn. This review work shows that advancing the incorporation of recycled aggregates in the manufacture of CBMUs needs additional concerted efforts in terms of research work, standards and codes of practice, education, and public awareness.