Permafrost affected soils are a key component of the global carbon cycle and play an important role in moderating the global climate system. Previous permafrost soil organic carbon (SOC) stock estimates used a variety of upscaling approaches and reported substantial uncertainties in the estimates. In this study, we used greater number of field observations (n = 2703) and spatially referenced data of soil-forming factors (topographic attributes, land cover types, climate, and bedrock geology) in a regression kriging framework to predict the spatial and vertical heterogeneity of SOC stocks across the northern circumpolar and Tibetan permafrost regions. This approach allowed us to take into account both the correlation between SOC and environmental factors and the spatial autocorrelation among SOC observations to make separate estimates of SOC stocks and their spatial uncertainties (90% CI) for three depth intervals at 250-m spatial resolution. In the northern circumpolar region, we estimated 510 (449 – 572), 345 (297– 397), and 355 (324 – 401) Pg C for 0 – 1, 1 – 2, and 2 – 3 m depth intervals, respectively. In the Tibetan region, our estimates were 11 (9 – 13), 3 (0.5 – 6), and 3 (1– 5) Pg C at 0 – 1, 1 – 2, and 2 – 3 m depth intervals, respectively. We captured large spatial variability (coefficient of variation = 13 – 127%) depending upon the study region and depth interval. We found the greatest uncertainty range at 1 – 2 m depth in both permafrost regions. Soil wetness index and elevation were significant controllers of SOC stocks in both regions. Surface air temperature and bedrock geology were significant controllers of permafrost SOC in the circumpolar region, whereas precipitation was a significant controller in the Tibetan region. Flat areas (<2% slope angle) stored the greatest amount of SOC in the northern circumpolar region, but hill toe-slope positions stored the largest SOC stocks in the Tibetan region. In the circumpolar region, the greatest topographic uncertainty in SOC stocks (27%) was in hill toe-slope positions. In the Tibetan region, however, the uncertainty was highest (62%) in flat areas. We hope our spatially explicit estimates of SOC stocks can be useful for initializing and benchmarking the representation of SOC stocks in regional and global land surface models.