Increased permafrost temperatures have been reported in the circum-Arctic, and widespread degradation of permafrost peatlands has occurred in recent decades. The timing of permafrost aggradation in these ecosystems could have implications for the soil carbon lability upon thawing, and an increased understanding of the permafrost history is therefore needed to better project future carbon feedbacks. In this study, we have conducted high-resolution plant macrofossil and geochemical analyses and accelerator mass spectrometry radiocarbon dating of active layer cores from four permafrost peatlands in northern Sweden and Norway. In the mid-Holocene, all four sites were wet fens, and at least three of them remained permafrost-free until a shift in vegetation toward bog species was recorded around 800 to 400 cal. BP, suggesting permafrost aggradation during the Little Ice Age. At one site, Karlebotn, the plant macrofossil record also indicated a period of dry bog conditions between 3300 and 2900 cal. BP, followed by a rapid shift toward species growing in waterlogged fens or open pools, suggesting that permafrost possibly was present around 3000 cal. BP but thawed and was replaced by thermokarst.