Permafrost is tightly coupled to the organic soil layer, an interaction that mediates permafrost degradation in response to regional warming. We analyzed changes in permafrost occurrence and organic layer thickness (OLT) using more than 3000 soil pedons across a mean annual temperature (MAT) gradient. Cause and effect relationships between permafrost probability (PF), OLT, and other topographic factors were investigated using structural equation modeling in a multi-group analysis. Groups were defined by slope, soil texture type, and shallow (<28 cm) versus deep organic (≥28 cm) layers. The probability of observing permafrost sharply increased by 0.32 for every 10-cm OLT increase in shallow OLT soils (OLTs) due to an insulation effect, but PF decreased in deep OLT soils (OLTd) by 0.06 for every 10-cm increase. Across the MAT gradient, PF in sandy soils varied little, but PF in loamy and silty soils decreased substantially from cooler to warmer temperatures. The change in OLT was more heterogeneous across soil texture types—in some there was no change while in others OLTs soils thinned and/or OLTd soils thickened at warmer locations. Furthermore, when soil organic carbon was estimated using a relationship with thickness, the average increase in carbon in OLTd soils was almost four times greater compared to the average decrease in carbon in OLTs soils across all soil types. If soils follow a trajectory of warming that mimics the spatial gradients found today, then heterogeneities of permafrost degradation and organic layer thinning and thickening should be considered in the regional carbon balance.