Shotcrete permanent support structure of long highway tunnels in high-latitudes and high-altitudes area is subjected to the action of freeze-thaw damage and carbonation which degraded structure durability performance and increased the tunnel maintenance and operation cost. Carbonation durability of frost-damaged-shotcrete was investigated by using freeze-thaw cycles in air firstly and then accelerated carbonation method. With the evaluating indicator of carbonation depth and relative compressive strength, the deterioration law and influence factor of carbonation depth and relative compressive strength on frost damage shotcrete specimens were researched. Results show that frost damage accelerated the carbonation rate and carbonation depth was deeper with the relative dynamic elasticity modulus decreased. The relative compressive strength of frost damage shotcrete increased with the increasing of carbonation depth. However, when frost damage degree was more than 10%, the influence of relative compressive strength on frost damage shotcrete was not obvious. Furthermore, the carbonation depth prediction model of shotcrete was established considering frost damage degree, shotcrete mixture parameters and concrete forming mode, respectively. The overall error between the predicted value and the experimental data was less than 20%, and the standard error was 0.16.