Uniaxial compression tests were carried out on cement soils and fly ash soils after the freeze-thaw cycling. The effects of the number of freeze-thaw cycles, curing period, and moisture condition on the mechanical properties of soils were investigated. The failure mechanism of soils due to freeze-thaw cycling was studied as well. The results indicated that the freeze-thaw cycling decreases the compressive strength of cement soils, especially at a large number of freeze-thaw cycles, whereas decreasing the compressive strength of fly ash soils at an early stage. The frost resistance of soils increases as the curing period increases. For a given number of freeze-thaw cycles, the compressive strength of soils with lower moisture content is greater than those with higher moisture content. Fly ash has smaller particle sizes than cement, and therefore has better performance in filling soil pores. Since the freezing temperature decreases as the pore size decreases, fly ash soils have a better frost resistance than cement soils. In actual engineering project, proper methods used to improve the frozen soils should be chosen according to the different environment of the projects, so as to meet the engineering requirements.