Rocks in cold regions tend to experience exacerbated degradation under the combined effects of environmental and anthropogenic factors, which may arise from, for example, temperature fluctuation, mechanical excavation, and blasting. Activities related to rock support or open-pit slope optimization in cold regions require a complete understanding of the failure mechanisms of rock under the complex conditions. This paper quantitatively documents the impact of combined cyclic mechanical load and freeze-thaw cycles (i.e., the effect of stress “history”) on the microstructural evolution and mechanical degradation of three porous sandstones with distinct porosity values (from 3.9 to 14.1%). The three sandstone samples were collected from different geological regions in China. The microstructural evolution of the tested samples was quantitatively analyzed using the low-field Nuclear Magnetic Resonance (NMR) technique. To investigate sample degradation arising from the impact of the stress “history”, the cyclic-loaded and freeze-thaw cycled samples were eventually compressed to failure, during which an acoustic emission system was used to monitor microseismic activities. The results of the study show that the porosity of all tested sandstone samples was increased after cyclic load, with a much more rapid and further increase in porosity observed for samples being subsequently treated under the freeze-thaw cycles. More interestingly, the Chuxiong sandstone with relatively small porosity values were much more sensitive to the impact of cyclic load compared with the Linyi sandstone, exhibiting a somewhat larger increase rate in porosity. However, the Linyi sandstone with larger initial porosity values exhibited a relatively large increase rate in porosity under the multiple freeze-thaw treatments. The multiple freeze-thaw treatments mainly resulted in the development of relatively large pores. The results of the uniaxial compression tests show that the strength reduction of the samples being solely treated by freeze-thaw cycles was within the range of 5–10%, whereas it was within the range of 20–40% for those samples subjected to the combined cyclic load and freeze-thaw cycles.