Bond defects at rubber-cement matrix interface are detrimental to durability of the cement composite. Therefore, coating rubber aggregates with copolymer has been suggested to overcome this defect. This paper aims to investigate the effect of an improved rubber-cement matrix bond on frost resistance. Freeze-thaw temperature cycles were controlled by a thermal sensor embedded inside the core of a mortar specimen. Measurements of relevant quantities, such as mass loss, length change, mechanical properties (relative dynamic modulus of elasticity, compressive and flexural strengths), and durability factor, demonstrated that rubberized cement-based materials were more resistant under freeze-thaw environments than the control one. Especially, regardless of slight length gain of mortar incorporating coated rubber aggregates, copolymer coating still made the composite durable in frost conditions owing to its improved strain capacity and higher residual post-peak tensile strength.