Structural failures due to excess dead-weight pause critical challenges in the structural integrity and safety in the construction industry. The quantity of dead load is usually well ascertained during the design step and has a long-term permanent effect on the structural behavior. Any reduction in the dead load due to the change of building materials can be viewed as an opportunity to ascertain the structural health, economic benefit, and environmental compliance. Present study investigates the suitability of three types of nanomaterials (lime—CaO, gypsum—CaSO4.2H2O and aluminum oxide—Al2O3) along with fly ash as potential replacements to cement (by 5–20%) for preparing lightweight building blocks by optimizing their proportions and testing their performances. The test results showed that an equi-molar mixture of lime, gypsum, and alumina along with fly ash exhibited higher compressive strength and durability compared to the other mixtures. The selection of appropriate combination of nanoparticles is found to be critical in ensuring the desired engineering properties for the casted specimens. Further, the study advocates reuse of industrial wastes for preparing building elements thereby helping to achieve circular economy in the construction industry.