Utilizing relative dynamic elastic modulus and weight loss of concrete as evaluation indices, the frost resistance of concrete with 0.45 water-cement ratio and different recycled aggregate replacement proportions was studied in the water and 3.5% sodium chloride solution. The mass proportions of recycled aggregate are 25%, 50% and 75%, respectively. Furthermore, the frost resistance of the modified concrete with 5% and 10% rubber powder volume fractions replacing fine aggregates was studied. The results show that: the frost resistance of concrete decreases with the increase of recycled aggregate, when the recycled aggregate mass fractions are 25% and 50%, its influence on the frost resistance of concrete is little, and mixing rubber powders can effectively improve the frost resistance of concrete; when the recycled aggregate mass fraction reaches 75%, its effect on the frost resistance of concrete is significant, and mixing rubber powders has certain improvement effect, but compared with the benchmark group of concrete the maximum freeze-thaw cycles decreases more than 30%. In water frozen test, the weight loss is small and the relative dynamic elastic modulus loss is quite obvious. The frost resistance is better when adding 5% volume fraction of rubber powders. In salt frozen test, the main characteristic is the weight loss exceeds the requirements. The frost resistance is better when adding 10% volume fraction of rubber powders. The improvement effect of rubber powder to the frost resistance of concrete in salt solution is much better than that in water.