This paper presents a Reliability-Based Design Optimization (RBDO) for Deep Mixing Walls (DMW), taking into account parameter uncertainties, required safety levels and construction costs. A procedure that integrates Polynomial Chaos Kriging (PCK) and constrained (1 + 1) Covariance Matrix Adaptation Evolution Strategy (constrained (1 + 1)-CMA-ES) is proposed, referred to as PCK-RBDO-ES, for the optimization of DMW design. Specifically, PCK is employed to reduce required numerical simulations and improve efficiency of reliability assessments, while the constrained (1 + 1)-CMA-ES method is used for global optimization of design parameters. Unconfined Compressive Strength (UCS) is considered as the design variable to be optimized in this study and an existing DMW was selected as a reference case. The PCK-RBDO-ES results are first presented and compared to validate the effectiveness and efficiency. Then, the influence of the DMW uncertainties and adjacent soil uncertainties on the UCS evaluations is discussed, and the effect of the target reliability requirement is further investigated. The results indicate that the proposed PCK-RBDO-ES procedure is effective and provides useful insights for DMW design and construction. Uncertainties on UCS and stiffness of DMW, as well as on the friction angle of soft to medium clay layer, are shown to have significant impacts on the design optimization. This study can help designers to manage project risks, and facilitate risk-aware and cost-effective decision-making.