High temperature treatment is a typical detrimental situation that may significantly influence the compressive strength of cement-based materials. It was reported that the incorporation of common waste materials as supplementary cementitious materials (SCMs) can improve high temperature resistance. In this work, fly ash (FA), granulated blast-furnace slag (GGBFS), and silica fume (SF) were used as SCMs to replace cement to produce green cement-based materials. The mechanical strengths of the samples being subjected to various elevated temperatures were measured and analyzed with different SCMs contents. Results showed that when the high temperature was above 500 °C, it caused significant loss of strength, and the use of SCMs can improve the high temperature resistance of the cement-based materials with higher residual strength, especially for the GGBFS and SF blended samples. Moreover, the random forest regression algorithm was used to predict the compressive strength for the cement-based material incorporating various waste materials, and exhibited high accuracy. This work presents a comprehensive study on the regularity of changes of mechanical strength and provides a specific algorithm for the precise prediction of this occurrence, which is helpful to understand and predict the influence of high temperature treatment on green cement-based materials with various waste materials.