The counterfort retaining wall is one of the most frequent structures used in civil engineering. In this structure, optimization of cost and CO2 emissions are important. The first is relevant in the competitiveness and efficiency of the company, the second in environmental impact. From the point of view of computational complexity, the problem is challenging due to the large number of possible combinations in the solution space. In this article, a k-means cuckoo search hybrid algorithm is proposed where the cuckoo search metaheuristic is used as an optimization mechanism in continuous spaces and the unsupervised k-means learning technique to discretize the solutions. A random operator is designed to determine the contribution of the k-means operator in the optimization process. The best values, the averages, and the interquartile ranges of the obtained distributions are compared. The hybrid algorithm was later compared to a version of harmony search that also solved the problem. The results show that the k-mean operator contributes significantly to the quality of the solutions and that our algorithm is highly competitive, surpassing the results obtained by harmony search.