The degradation of modern and ancient permafrost-affected soils and organic-rich sediments and the release of relict soil organic matter from the frozen state are critical for understanding the global carbon cycle in a changing climate. The molecular structure of humic acids isolated from modern Cryosols and paleosoils from the Ice Complex deposits in the Batagay megaslump area was investigated. The elemental composition analysis was performed using a CHN analyzer, and molecular composition analysis was determined by CP/MAS 13C-NMR spectroscopy. Analysis of the molecular structure of humic acids showed that MIS 5e paleosoils are characterized by a relatively high content of aliphatic structural fragments (C,H-AL—29–36%) and a low content of aromatic structural fragments (AR/AL—0.49–0.43), which reveals low humification rates in this time period. The composition of humic acids from MIS 7 paleosoils shows a relatively high content of aromatic structural fragments compared to modern soils (AR/AL—0.47) and MIS 5e deposits (AR/AL—0.67–0.54), indicating a longer humification process in heterogenic conditions (warm and cold periods). The results indicate that the molecular structure of humic acids is a dynamic parameter of the environment that reflects the local conditions of pedogenesis and organic matter formation. Permafrost thawing leads to the release of organic matter (including matter that is relatively weakly resistant to biodegradation where aliphatic structural fragments dominate the composition of humic acids) that may strengthen the emission of climate-active gases into the atmosphere and boost climate change.