Coal gangue concrete in high, cold mines in western China is subject to freeze–thaw damage due to prolonged low temperatures and large temperature variations, leading to surface spalling, cracking, and degradation of mechanical performance. In this study, four coal gangue concrete mixtures with replacement ratios of 0%, 20%, 40%, and 60% were prepared using gangue from the Halagou Mine in the Shendong area. Freeze–thaw cycle tests were conducted to analyze the effects of the replacement rate and number of cycles on compressive strength, elastic modulus, and peak strain. The results show that both compressive strength and elastic modulus decrease with increasing freeze–thaw cycles, while the peak strain increases. After 80 cycles, the compressive strength of the M0, M20, and M40 groups decreased by 35.0%, 41.8%, and 51.1%, respectively, and their elastic modulus dropped by 49.2%, 86.2%, and 92.0%. The M60 group was too severely damaged to be tested. Based on the experimental data, a constitutive model for coal gangue concrete under freeze–thaw conditions was developed and validated using Abaqus finite element analysis, with simulation errors below 10%. Considering both mechanical performance and resource utilization, the optimal coal gangue replacement rate is determined to be 20%.