Conventional fire bricks contaminate the environment as well as induce land subsidies due to illegal mining activity, especially in hilly terrains with rapid growth in construction. Though researchers employed industrial waste by-products like fly ash in the production of blocks as a replacement, it is confined to a certain extent by inducing ordinary Portland cement (OPC). The current chapter investigates the influence of gypsum on compressive strength characteristics of solid interlocking blocks prepared from waste by-products FA and quarry dust. The test specimens were subjected to compressive strength with a curing period of 28 days. From the test results, the maximum compressive strength of 8.5 MPa is obtained at a curing period of 28 days with optimum content of 6% cement and 4% gypsum along with 50% FA, 30% quarry dust, and 10% of 6 mm aggregates (i.e., CG-2), which is comparatively greater than the conventional bricks. The obtained compressive strength is complying the requirement stated by IS1077 (i.e., 3.5 MPa) and IS-3495 (Part1) (i.e., 7.5 MPa). These blocks can be used as an alternative for red brick masonry in construction. The cost comparison with conventional red bricks revealed that the interlocking blocks are cheaper than the convention red bricks and reduced the construction cost by 33%. It does not require any cement mortar for bonding and plastering, which reduces cement consumption by 20–30%.