Anti-carbonization performance is an important durability indicator of recycled high performance concrete in atmosphere. An orthogonal experiment was designed in this paper considering water-cement ratio, recycled coarse and fine aggregate, slag, fly ash, carbonization time, as well as the stress level under load. Experimental results showed that (1) water-cement ratio and the amount of cement relate to the degree of hydration of concrete and density, thereby affect the anti-carbonation performance of concrete; (2) carbonation depth has a positive correlation between the carbonization and the square root of the time; and (3) carbonization depth will increase under tensile stress.