Considering the well known environmental issues of cement manufacturing (direct and indirect levels of $CO_2$ emissions), clinker replacement by supplementary cementing materials (SCM) can be a very promising first step in reducing considerably the associated emissions. However, such a reduction is possible up to a particular level of SCM utilization, influenced by the rate of its pozzolanic reaction. In this study a (4-step) structured methodology is proposed in order to be able to further adjust the concrete mix design of a particular SCM, in achieving additional reduction of the associated levels of $CO_2$ emissions and being at the same time accepted from a derived concrete strength and service life point of view. On this note, the aim of this study is twofold. To evaluate the environmental contribution of each concrete component and to provide the best possible mix design configuration, balanced between the principles of sustainability (low environmental cost) and durability (accepted concrete strength and service life ). It is shown that such a balance can be achieved, by utilising SCM by-products in the concrete mix, reducing in this way the fixed environmental emissions without compromising the long-term safety and durability of the structure.