In Tanzania, construction and demolition (C&D) waste is not recycled and knowledge on how it can be recycled especially into valuable products like building materials are still limited. This study aimed at investigating the possibility of recycling the C&D waste (mainly cementitious rubble) into building material in Tanzania. The building materials produced from C&D waste was concrete blocks. The concrete blocks were required to have a load bearing capacity that meets the building material standards and specifications. Eight C&D waste samples were collected from C&D building sites, transported to the recycling site, crushed, and screened (sieved) to get the required recycled aggregates. Natural aggregates were also used as control. The recycled aggregates were tested in the laboratory following the standard methods as specified in Tanzanian standards. The physical, mechanical and chemical characteristics were determined. The physical and mechanical results showed that recycled aggregates were weaker than natural aggregates. However, chemically they were close to natural aggregates and therefore suitable for use in new concrete block production. In the production process, each experiment utilized 100% recycled aggregates for both fine and coarse portions to replace natural aggregates. The Fuller’s maximum density theory was used to determine the mix proportions of materials in which a method that specifies concrete mix by system of proportion or ratio was used. The concrete blocks production processes included batching, mixing (that was done manually to get homogeneous material), compacting and moulding by hand machine and curing in water. After 28 days of curing, the concrete blocks were tested in the laboratory on compressive strength, water absorption ratio and density. The results showed that the blocks produced with 100% recycled aggregates were weaker than those with natural aggregates. However, the results also showed that there is a possibility of recycling the C&D waste into building material because 85% of the tested concrete block specimens from recycled aggregates achieved a compressive strength of 7 N/mm2, which is defined as the minimum required load bearing capacity in Tanzania. Therefore, the C&D waste could be a potential resource for building material production for sustainable construction in Tanzania rather than discarding it. Further work should focus on the economic feasibility of production of concrete blocks with recycled aggregates in Tanzania.