<p>The Cenozoic red-bed of the northeastern Tibetan Plateau constitute disaster-prone strata. Massive catastrophic events within these red-bed are primarily driven by multi-scale structural deterioration resulting from freeze-thaw (F-T) cycles. Consequently, a comprehensive investigation into multi-scale deterioration effects during F-T cycles is critical to understanding these catastrophic processes. This study focuses on the Cenozoic red-bed mudstone in the Guide Basin of the northeastern Tibetan Plateau. X-ray diffraction (XRD), scanning electron microscopy (SEM), computed tomography (CT), and triaxial shear testing were used to analyze the mineral composition, microstructure, mesostructure, and strength evolution of the samples. Through these analyses, the multi-scale deterioration mechanisms under F-T conditions were elucidated. XRD analysis reveals that F-T cycles alter the mineral composition of the samples, primarily due to the hydrolysis of albite into kaolinite. SEM observations show an increase in porosity and macropore content, along with the expansion and interconnection of microfractures, forming a damage network. CT scans further demonstrate an initial increase in porosity followed by a decrease, while the fracture rate steadily increases, reflecting the transition from pores to fractures. These structural changes significantly degrade mechanical properties. The deterioration coefficients of cohesion (<i>c</i>), internal friction angle (<i>φ</i>), and elastic modulus (<i>E</i>) are 0.53 (95% CI: 0.49–0.57), 0.57 (95% CI: 0.53–0.60), and 0.27 (95% CI: 0.24–0.30), respectively. Thus, the deterioration process of Cenozoic red-bed mudstone can be summarized as “micropore expansion, macropore interconnection, and fracture network formation”. These findings will provide theoretical insights for disaster prevention and engineering practices within the basin and similar regions.</p>