Many studies on the mixture design of fly ash and slag ternary blended concrete have been conducted. However, these previous studies did not consider the effects of climate change, such as acceleration in the deterioration of durability, on mixture design. This study presents a procedure for the optimal mixture design of ternary blended concrete considering climate change and durability. First, the costs of CO emissions and material are calculated based on the concrete mixture and unit prices. Total cost is equal to the sum of material cost and CO emissions cost, and is set as the objective function of the optimization. Second, strength, slump, carbonation, and chloride ingress models are used to evaluate concrete properties. The effect of different climate change scenarios on carbonation and chloride ingress is considered. A genetic algorithm is used to find the optimal mixture considering various constraints. Third, illustrative examples are shown for mixture design of ternary blended concrete. The analysis results show that for ternary blended concrete exposed to an atmospheric environment, a rich mix is necessary to meet the challenge of climate change, and for ternary blended concrete exposed to a marine environment, the impact of climate change on mixture design is marginal.