This study utilized X-ray computed tomography (CT) technology to analyze the meso-structure of concrete at different replacement rates, using a coal gangue coarse aggregate, after experiencing various freeze–thaw cycles (F-Ts). A predictive model for the degradation of the elastic modulus of Coal Gangue coarse aggregate Concrete (CGC), based on mesoscopic damage, was established to provide an interpretation of the macroscopic mechanical behavior of CGC after F-Ts damage at a mesoscopic scale. It was found that after F-Ts, the compressive strength of concrete, with coal gangue replacement rates of 30%, 60%, and 100%, respectively, decreased by 33.76%, 34.89%, and 42.05% compared with unfrozen specimens. The results indicate that an increase in the coal gangue replacement rate exacerbates the degradation of concrete performance during the F-Ts process. Furthermore, the established predictive formula for elastic modulus degradation closely matches the experimental data, offering a reliable theoretical basis for the durability design of CGC in F-Ts environments.