The utilization of recycled aggregates (RA) for concrete production has the potential to offer substantial environmental and economic advantages. However, RA concrete is plagued with considerable durability concerns, particularly carbonation. To advance the application of RA concrete, the establishment of a reliable model for predicting the carbonation is needed. On the one hand, concrete carbonation is a long and slow process and thus consumes a lot of time and energy to monitor. On the other hand, carbonation is influenced by many factors and is hard to predict. Regarding this, this paper proposes the use of machine learning techniques to establish accurate prediction models for the carbonation depth (CD) of RA concrete. Three types of regression techniques and meta-heuristic algorithms were employed to provide more alternative predictive tools. It was found that the best prediction performance was obtained from extreme gradient boosting-multi-universe optimizer (XGB-MVO) with R² value of 0.9949 and 0.9398 for training and testing sets, respectively. XGB-MVO was used for evaluating physical laws of carbonation and it was found that the developed XGB-MVO model could provide reasonable predictions when new data were investigated. It also showed better generalization capabilities when compared with different models in the literature. Overall, this paper emphasizes the need for sustainable solutions in the construction industry to reduce its environmental impact and contribute to sustainable and low-carbon economies.