The reuse of industrial waste plays a vital role in sustainable development in recent years. In this study, the potential of using the densified mixture design algorithm (DMDA) to utilize waste incineration fly ash (IFA) as a cementitious replacement in interlocking concrete brick (ICB) was investigated. The differences in dimensions, visible defects, engineering properties, and long-term performance of ICB samples produced using different IFA replacement ratios (0%, 15%, 30%, 45%, and 60%) were examined. The results indicate that the IFA replacement level affects ICB properties significantly with increasing levels of IFA replacement associated with decreasing compressive strength, abrasion resistance, bending strength, and bulk density whereas increasing water absorption and void volume. The results of a scanning electron micrograph analysis indicate that higher IFA content is associated with a progressively less-homogeneous microstructure. The effectiveness of the DMDA algorithm was clearly verified, as all of the samples were found to comply fully with relevant Vietnamese standards. The relationships among the tested properties were then established and discussed. The findings of this study prove a promising approach for the combination DMDA algorithm and IFA materials in the production of interlocking bricks adapting sustainable development.