Steel fiber and basalt fiber can effectively improve the durability of concrete. Using the freeze-thaw cycle test, the steel and basalt fiber reinforced concrete frost resistance and freeze-thaw damage calculation model were studied. The results show that the frost resistance of concrete is obviously affected by the fiber type and fiber volume. When the volume fraction is 1.5% steel fiber and 0.05% basalt fiber, the frost resistance of concrete is the best, which can reach the level of F250. The freezing and thawing damage mechanism and the enhancement of fiber were analyzed, which determined the freeze-thaw damage calculation model based on relative elastic modulus and freeze-thaw cumulative damage. Based on the comparative analysis of the experimental data, it is concluded that the freeze-thaw damage calculation model based on the relative dynamic elastic modulus is more accurate. The decay mode of the quadratic function is better than that of the exponential function decay mode. The correlation coefficient of the quadratic function decay mode reached 0.99 or higher, which is more suitable for predicting the freeze-thaw durability of fiber concrete.