Ice-rich Pleistocene-age permafrost is particularly vulnerable to rapid thaw, which may quickly expose a large pool of sedimentary organic matter (OM) to microbial degradation and lead to emissions of climate-sensitive greenhouse gases. Protective physico-chemical mechanisms may, however, restrict microbial accessibility and reduce OM decomposition; mechanisms that may be influenced by changing environmental conditions during sediment deposition. Here we study different OM fractions in Siberian permafrost deposited during colder and warmer periods of the past 55,000 years. Among known stabilization mechanisms, the occlusion of OM in aggregates is of minor importance, while 33-74% of the organic carbon is associated with small, <6.3 µm mineral particles. Preservation of carbon in mineral-associated OM is enhanced by reactive iron minerals particularly during cold and dry climate, reflected by low microbial CO2 production in incubation experiments. Warmer and wetter conditions reduce OM stabilization, shown by more decomposed mineral-associated OM and up to 30% higher CO2 production. This shows that considering the stability and bioavailability of Pleistocene-age permafrost carbon is important for predicting future climate-carbon feedback.