The construction industry is a major contributor to environmental pollution, with cement production only accounting for nearly 8% of global CO2 emissions. Sustainable alternatives, such as bio-bricks incorporating agricultural waste, offer a promising solution to reduce emissions. This study investigates the development and optimization of bio-bricks using lignin as reinforcement in cementitious composites. A mixture design approach was applied to determine optimal proportions of cement, lignin, and bovine excreta, enhancing mechanical properties such as compressive and flexural strength while promoting sustainability. Response Surface Methodology (RSM) was used to model the effects of mixture components, revealing that a blend of 959 g of cement, 224 g of lignin, and 314 g of bovine excreta resulted in the best performance. Compressive strength reached ~1.7 MPa, demonstrating the composition viability for eco-friendly construction. The study highlights the bio-brick’s potential to mitigate the environmental impact by reducing reliance on traditional cement while integrating renewable materials.