To minimize the environmental risks and for sustainable development, the utilization of recycled aggregate (RA) is gaining popularity all over the world. The use of recycled coarse aggregate (RCA) in concrete is an effective way to minimize environmental pollution. RCA does not gain more attraction because of the availability of adhered mortar on its surface, which poses a harmful effect on the properties of concrete. However, a suitable mix design for RCA enables it to reach the targeted strength and be applicable for a wide range of construction projects. The targeted strength achievement from the proposed mix design at a laboratory is also a time-consuming task, which may cause a delay in the construction work. To overcome this flaw, the application of supervised machine learning (ML) algorithms, gene expression programming (GEP), and artificial neural network (ANN) was employed in this study to predict the compressive strength of RCA-based concrete. The linear coefficient correlation (R2), mean absolute error (MAE), mean square error (MSE), and root mean square error (RMSE) were evaluated to investigate the performance of the models. The k-fold cross-validation method was also adopted for the confirmation of the model’s performance. In comparison, the GEP model was more effective in terms of prediction by giving a higher correlation (R2) value of 0.95 as compared to ANN, which gave a value of R2 equal to 0.92. In addition, a sensitivity analysis was conducted to know about the contribution level of each parameter used to run the models. Moreover, the increment in data points and the use of other supervised ML approaches like boosting, gradient boosting, and bagging to forecast the compressive strength, would give a better response.