Applying soft computing models for solving real-life problems has yielded many significant benefits, especially in the mining industry. This study proposed a novel soft computing model for estimating blast-induced air over-pressure (AOp) with high accuracy. Accordingly, the boosted smoothing spline (BSTSM) and genetic algorithm (GA) were considered and combined, namely GA-BSTSM model. One hundred twenty-one blasts were collected at the Coc Sau open-pit coal mine (Vietnam) for this aim. The explosive capacity used (W) and distance (R) were considered as the primary input variables for the aiming of AOp prediction. Also, the meteorological conditions such as temperature (T), relative humidity (RH), atmospheric pressure (AP), wind speed (WS), and wind direction (WD) were taken into account to predict AOp in this study. To confirm the performance of the proposed GA-BSTSM model, an empirical model and six other artificial intelligence models were also developed to predict AOp based on the same dataset, including CART (classification and regression tree), KNN (k-nearest neighbors), ANN (artificial neural network), BRR (Bayesian ridge regression), SVR (support vector regression), and Gaussian process (GP). The developed models were then evaluated through three performance indices (i.e., RMSE, R², and VAF) using the testing dataset. In addition, a Taylor diagram was also developed to evaluate the quality of the models. The evaluation results showed that the proposed GA-BSTSM model yielded a robust performance with high accuracy for AOp prediction herein. The findings also disclosed that meteorological factors have a strong influence on the accuracy of AOp predictive models, especially RH and WS.