Vegetation shifts in circum-Arctic permafrost peatlands drive feedbacks with important consequences for peatland carbon budgets and the extent of permafrost thaw under changing climate. Recent shrub expansion across Arctic tundra environments has led to an increase in above-ground biomass, but the long-term spatiotemporal dynamics of shrub and tree growth in circum-Arctic peatlands remain unquantified. We investigate changes in peatland vegetation composition during the Holocene using previously-published plant macrofossil records from 76 sites across the circum-Arctic permafrost zone. In particular, we assess evidence for peatland shrubification at the continental scale. We identify increasing abundance of woody vegetation in circum-Arctic peatlands from ∼8000 years BP to present, coinciding with declining herbaceous vegetation and widespread Sphagnum expansion. Ecosystem shifts varied between regions and present-day permafrost zones, with late-Holocene shrubification most pronounced where permafrost coverage is presently discontinuous and sporadic. After ∼600 years BP, we find a proliferation of non-Sphagnum mosses in Fennoscandia and across the present-day continuous permafrost zone; and rapid expansion of Sphagnum in regions of discontinuous and isolated permafrost as expected following widespread fen-bog succession, which coincided with declining woody vegetation in eastern and western Canada. Since ∼200 years BP, both shrub expansion and decline were identified at different sites across the pan-Arctic, highlighting the complex ecological responses of circum-Arctic peatlands to post-industrial climate warming and permafrost degradation. Our results suggest that shrubification of circum-Arctic peatlands has primarily occurred alongside surface drying, resulting from Holocene climate shifts, autogenic peat accumulation, and permafrost aggradation. Future shrubification of circum-Arctic peatlands under 21st century climate change will likely be spatially heterogeneous, and be most prevalent where dry microforms persist.