The waste tire rubber may be incorporated with the cement soil to improve its frost resistance. However, it remains a significant challenge to optimise the rubber content between its mechanical strength and durability under freeze-thaw conditions. In this study, the macroscopic mechanical properties of ordinary cement soil and rubber-cement soil (with particle sizes of 30 and 60 mesh) were explored under different freeze-thaw cycles (0, 3, 6, 9, 15) by taking the wave propagation and unconfined compressive strength (UCS) tests. Subsequently, a series of scanning electron microscope (SEM) and X-ray diffraction (XRD) tests were conducted to analyse the microstructure of the specimens, further clarifying the freeze-thaw damage mechanisms in rubber-cement soil. The results show that freeze-thaw cycles cause irreversible internal damage to the cement soil, leading to continuous reductions in both wave velocity and UCS. After 15 freeze-thaw cycles, the wave velocity loss rates are 95%, 72.2%, and 89.7% for ordinary cement soil, cement soil mixed with 30-mesh and 60-mesh rubber particles, respectively. The corresponding UCS loss rates are 95.4%, 82.7%, and 89.2%, respectively. The above results suggest that 30-mesh rubber-cement soil exhibits superior frost resistance. From a microstructural perspective, the rubber particles delay and inhibit the propagation of frost heaving cracks, forming a denser spatial structure for calcium silicate hydrates (C-S-H) gel, thereby improving the freeze-thaw resistance. By integrating macroscopic mechanical testing and microstructural analysis, this study reveals the mechanical properties and damage mechanism of rubber-cement soil under freeze-thaw conditions, providing valuable insights for its engineering applications.