At the Last Glacial Maximum (LGM), after ~100,000 years of relatively cold temperatures and progressively lower atmospheric carbon dioxide (CO₂) concentrations, CO₂ levels reached ~180 ppm, which is less than half of what we see today in a much warmer world (~400 ppm). Although much of this increase since the LGM is due to human-induced emissions, about 100 ppm of this increase can be attributed to natural variations seen over glacial to interglacial cycles. The sources for this natural CO₂ rise remain unclear despite considerable efforts to constrain its origin. This thesis attempts to describe and quantify the role of soil carbon in this context, with emphasis on the permafrost hypothesis, which states that a shift from glacial to interglacial conditions released permafrost soil carbon to the atmosphere during the deglaciation. We present empirical estimates of the change in the Northern permafrost area between the LGM and present, and the associated soil carbon stock changes. We also partition these soil carbon stock changes at millennial intervals to capture not only the size but the timing of change. We find that the soil carbon stocks north of the Tropics decreased after the LGM to reach a minimum around 10,000 years ago, after which stocks increased to more than compensate for past losses. This may present part of a solution to untangle the marine and atmospheric ¹³C record, where the marine records suggest that the terrestrial carbon stock has grown since the LGM, while the atmospheric record also indicates terrestrial losses. To estimate the mineral soil carbon stocks, we have relied on vegetation reconstructions. Some of these reconstructions were created with a novel data-driven machine learning approach. This method may facilitate robust vegetation reconstruction when evidence of past conditions is readily available. Results in this thesis highlight the importance of permafrost, loess deposits and peatlands when considering the soil carbon cycle over long time scales.