Predicting pillar stability in underground mines is a critical problem because the instability of the pillar can cause large-scale collapse hazards. To predict the pillar stability for underground coal and stone mines, two new models (random tree and C4.5 decision tree algorithms) are proposed in this paper. Pillar stability depends on the parameters: width of the pillar (W), height of the pillar (H), W/H ratio, uniaxial compressive strength of the rock (σucs), and pillar stress (σp). These parameters are taken as input variables, while underground mines pillar stability as output. Various performance indices, i.e., accuracy, precision, recall, F-measure, Matthews correlation coefficient (MCC) were used to evaluate the performance of the models. The performance evaluation of the established models showed that both models were able to predict pillar stability with reasonable accuracy. Results of the random tree and C4.5 decision tree were also compared with available models of support vector machine (SVM) and fishery discriminant analysis (FDA). The results show that the proposed random tree provides a reliable and feasible method of evaluating the pillar stability for underground mines.