Strength and stiffness of stabilized/solidified (S/S) sediments are supposed to be degraded by freeze–thaw cycles (FTs) when applied in constructions in cold regions. In order to reveal the degradation mechanisms, FTs were first simulated on S/S sediments in the laboratory. Then, macrotests including unconfined compression strength (UCS) tests and direct shear tests were conducted on S/S sediments at different FTs to investigate the strength and stiffness changes and microanalyses including scanning electron microscope analysis (SEM), mercury intrusion porosimetry (MIP), and nitrogen adsorption porosimetry (NAP) to investigate the microstructure changes. Macrotests show that strength indexes decrease gradually, stiffness parameters and brittleness increase first and then decrease, the compaction stage of stress–strain curves diminishes first and then increases, the decrease rate of friction angle decelerates first and then accelerates, and the decrease rate of cohesion decelerates first and then keeps stable, for S/S sediments in FTs. Microanalyses have precisely captured the damage chain of S/S sediments: meso and macropores inside sediment aggregates expand gradually during FTs; as a result, sediment aggregates are fractured and stripped off from the solidification skeleton gradually; losing support of sediment aggregates, solidification skeletons are adjusted first and then collapsed when sediment aggregate fracture reaches a limit value. Based on macro and microfindings, a damage model to explain strength and stiffness degradations by microstructure damage is successfully established. Based on the established damage model, a reasonable idea is proposed for promoting the resistance of S/S sediments to FTs.