Fly ash and slag have been widely used to produce low-CO2 concrete. However, previous studies have not paid enough attention to the lower carbonation resistance of fly-ash-and-slag-blended concrete and the aggravations of carbonation due to climate change. This study proposes a technique for the design of fly-ash-and-slag-blended concrete considering carbonation durability coupled with various climate change scenarios. First, CO2 emissions are evaluated from concrete mixtures. Concrete strength and carbonation depth are evaluated using efficiency factors of fly ash and slag. A genetic algorithm (GA) is used to find the optimal mixture with the lowest CO2 emissions considering the requirements of strength, carbonation durability, and workability. Second, we clarify the effect of cost on the mixture design of low-CO2 concrete. A genetic algorithm is also used to find the optimal mixture with the lowest cost. We found that the optimal mixture with the lowest cost is different from that with the lowest CO2 emissions. Third, by adding the additional constraint of cost, Pareto optimal mixtures are determined, which consider both lower CO2 emissions and lower material cost. The analysis results show that carbonation durability is the control factor of mixture design of fly ash-slag blended concrete. To mitigate the challenge of climate change, the binder content of blended concrete should be increased.