Construction activities have been a primary cause for depleting natural resources and are associated with stern environmental impact. Developing concrete mixture designs that meet project specifications is time-consuming, costly, and requires many trial batches and destructive tests that lead to material wastage. Computational intelligence can offer an eco-friendly alternative with superior accuracy and performance. In this study, coal waste was used as a recycled additive in concrete. The flexural strength of a large number of mixture designs was evaluated to create an experimental database. A hybrid artificial neural network (ANN) coupled with response surface methodology (RSM) was trained and employed to predict the flexural strength of coal waste-treated concrete. In this process, four influential parameters including the cement content, water-to-cement ratio, volume of gravel, and coal waste replacement level were specified as independent input variables. The results show that concrete incorporating 3% recycled coal waste could be a competitive and eco-efficient alternative in construction activities while attaining a superior flexural strength of 6.7 MPa. The RSM-modified ANN achieved superior predictive accuracy with an RMSE of 0.875. Based on the experimental results and model predictions, estimating the flexural strength of concrete incorporating waste coal using the RSM-modified ANN model yielded superior accuracy and can be used in engineering practice to save the effort, cost, and material wastage associated with trial batches and destructive laboratory testing while producing mixtures with enhanced flexural strength.