The search for alternatives that can replace conventional materials extracted from nature is crucial for environmental sustainability. This is especially the case for construction and geotechnical engineering, as this sector is a major consumer of the planet’s natural resources. This paper explores the use of ore sand (OS) tailings with fine aggregate characteristics, which are generated during exploration of iron ore and usually stored in stacks, in terms of their potential for replacing conventional aggregates (gravel, natural sand, and limestone sand) used in interlocking paving blocks for light-traffic pavement. A comparative life cycle assessment (LCA, cradle-to-gate) approach was applied for aggregates in interlocking blocks produced using OS compared to blocks produced with conventional aggregates. The OS was able to replace 24wt% of conventional aggregates (100% limestone sand and 13.3% natural sand), while maintaining compressive-strength performance similar to that of the conventional block (35 MPa). For all eleven environmental-impact categories evaluated in the LCA, the block with OS has improved environmental performance compared to the conventional block. Through the creation and use of a scoring indicator (SI), it was possible to determine that the transport distance of the OS is a limiting factor for the environmental efficiency of the alternative block. Nonetheless, the incorporation of OS mitigates the impacts of block production on eutrophication, acidification, fresh water, human toxicity, and abiotic depletion. The use of tailings reduces the demand for natural resources, decreasing the environmental impact of production and promoting sustainable construction practices.