The production of building materials is one of the most polluting industries for the natural environment. To change this, solutions are being sought that can reduce the environmental impact of the construction industry. One such solution is the modification of cement mixes with the addition of supplementary cementitious materials (SCMs). Such materials include granite powder waste and fly ash. Granite powder waste is generated when processing granite rocks, and fly ash is produced by burning fossil fuels. Both materials cause significant environmental problems. Their addition to cement-based materials may not only improve the condition of the natural environment, but also reduce the amount of cement used by the construction industry. The possibilities of reducing the amount of cement in cement mixes by using these materials were determined. It was concluded that the combined use of these materials in cement mixes enables the achievement of better mechanical properties, a lower amount of consumed embodied carbon dioxide (ECO2), and a decreased price of the mix. In conclusion, the most favourable proportions of both materials in cement composites were identified with regards to mechanical and environmental aspects.