Due to numerous variables contributing to the compressive strength of recycled aggregate concrete (RAC), developing robust prediction models for RAC’s compressive strength is a tricky task. Thus, this article proposes a novel and accurate method for predicting RAC’s compressive strength, tackling this problem. Here, 531 data points with seven independent variables were collected from published literature, and 400 data points were obtained by conducting tests in the lab. The sensitivity analysis based on the maximal information coefficient was conducted to define the most important variables contributing to RAC’s compressive strength. The main dataset with 931 data points was divided into three clusters titled up cluster (UC), middle cluster (MC), and down cluster (DC) using the self-organizing map. The optimal number of clusters was determined using the nonlinear principal component analysis. Multiple multilayer perceptrons (MLPs) were trained, whereas each MLP predicted the data in a single cluster. The main dataset was also used to train a single MLP (SMLP). The results showed that multiple MLPs reached the R-value of 0.94, 0.95, and 0.97, whereas SMLP reached the R-value of 0.59, 0.8, and 0.69 for predicting data in UC, MC, and DC, respectively. Thus, multiple MLPs trained on clusters were significantly more accurate than the SMLP and previous single prediction models. This new method demonstrates higher accuracy than typical machine learning methods, as well as being less complex compared with methods, including deep learning. This novel technique can be reliable for predicting RAC’s compressive strength, other mechanical properties, and engineering materials.