Durability design of recycled high performance concrete (RHPC) is fundamental for improving the use rate and level of concrete waste as coarse recycled aggregate (CRA). We discussed a frost-durability-based mix proportion design method for RHPC using 100 % CRA and natural sand. Five groups of RHPC mixes with five strength grades (40, 50, 60, 70 and 80 MPa) were produced using CRA with four quality classes, and their workability, 28 d compressive strengths and frost resistances (measured by the compressive strength loss ratio and the relative dynamic modulus of elasticity) were tested. Relationships between the 28 d compressive strength, the frost resistance and the CRA quality characteristic parameter, water absorption, were then developed. The criterion of a CRA maximum water absorption limit value for RHPC was suggested, independent of its source and quality class. The results show that all RHPC mixes achieve the expected target workability, strength, and frost durability. The research results demonstrate that the application of the proposed method does not require trial testing prior to use.