As the recent permafrost thawing of northern Asia proceeds due to anthropogenic climate change, precise and detailed palaeoecological records from past warm periods are essential to anticipate the extent of future permafrost variations. Here, based on the modern relationship between permafrost and vegetation (represented by pollen assemblages), we trained a Random Forest model using pollen and permafrost data and verified its reliability to reconstruct the history of permafrost in northern Asia during the Holocene. An early Holocene (12–8 cal ka BP) strong thawing trend, a middle-to-late Holocene (8–2 cal ka BP) relatively slow thawing trend, and a late Holocene freezing trend of permafrost in northern Asia are consistent with climatic proxies such as summer solar radiation and Northern Hemisphere temperature. The extensive distribution of permafrost in northern Asia inhibited the spread of evergreen coniferous trees during the early Holocene warming and might have decelerated the enhancement of the East Asian summer monsoon (EASM) by altering hydrological processes and albedo. Based on these findings, we suggest that studies of the EASM should consider more the state of permafrost and vegetation in northern Asia, which are often overlooked and may have a profound impact on climate change in this region.