The goals of this paper are to study the frost resistance of steel slag concrete (SSC), research the damage mechanisms, and predict the service life of SSC in cold regions. First, the stability of steel slag (SS) was tested, and then SS samples with different treatment dosages were used as aggregates to replace natural aggregates of equal volumes in the preparation of C40 concrete. The microstructures of concrete and micro properties of cement hydration products were investigated in nanospace in this research. In addition, rapid frost resistance durability tests were carried out under laboratory conditions. The results revealed that the ordinary concrete (OC) exhibited a more serious damage phenomenon, and the mass loss and relative dynamic elastic modulus of OC were changed by 5.27 and 62.30%, respectively. However, with increases in the SS content, the losses in mass were lowered. Furthermore, the relative dynamic elastic modulus decreased less, and the frost resistance of the specimens was stronger. The range of mass loss rate was between 2.233 and 3.024%, and the relative dynamic elastic modulus range was between 74.92 and 91.09%. A quadratic function with a good fitting degree was selected to establish a freezing-thawing damage calculation model by taking the relative dynamic elastic modulus as the variable. Then, the freezing-thawing durability lifespan of concrete in the colder regions of northern China was successfully predicted by using the damage calculation model. The results of SSC 20–60 showed the better frost resistance durability when the content of SS sand was 20% and the dosage of SS stone was 60%. Its frost resistance lifespan was more than twice that of OC, which demonstrated that SS as an aggregate could effectively improve the frost resistance lifespan of concrete to a certain extent.