Nowadays, the construction sector has a strong negative impact on the environment. In order to reduce this impact, alternatives to conventional building materials should be found and used for sustainable construction. In this respect, earthen construction is a viable solution due to its low transformation process. Highly developed in Mayotte from the 1980s to the 2000s, the Compressed Earth Block (CEB) industry is now in decline on the island. Most of the current CEB production uses cement, manufactured off the island, as a hydraulic stabilizer, which has a significant environmental cost. In the literature, research has focused on the potential of bio-additives to improve some properties of earthen building materials, thus reducing the carbon footprint of the material. This study, conducted on Mayotte soil, considers the use of local bio-based and minimally processed by-products as bio-additives for CEB to improve their compressive strength. The effects of three bio-additives are studied for mass concentrations ranging from 1% to 20%. The results show that the bio-additives improve the compressive strength of CEB by up to 37%.