Climate change has a major impact on arctic and boreal terrestrial ecosystems as warming leads to northward treeline shifts, inducing consequences for heterotrophic organisms associated with the plant taxa. To unravel ecological dependencies, we address how long-term climatic changes have shaped the co-occurrence of plants and fungi across selected sites in Siberia. We investigated sedimentary ancient DNA from five lakes spanning the last 47,000 years, using the ITS1 marker for fungi and the chloroplast P6 loop marker for vegetation metabarcoding. We obtained 706 unique fungal operational taxonomic units (OTUs) and 243 taxa for the plants. We show higher OTU numbers in dry forest tundra as well as boreal forests compared to wet southern tundra. The most abundant fungal taxa in our dataset are Pseudeurotiaceae, Mortierella, Sordariomyceta, Exophiala, Oidiodendron, Protoventuria, Candida vartiovaarae, Pseudeurotium, Gryganskiella fimbricystis, and Trichosporiella cerebriformis. The overall fungal composition is explained by the plant composition as revealed by redundancy analysis. The fungal functional groups show antagonistic relationships in their climate susceptibility. The advance of woody taxa in response to past warming led to an increase in the abundance of mycorrhizae, lichens, and parasites, while yeast and saprotroph distribution declined. We also show co-occurrences between Salicaceae, Larix, and Alnus and their associated pathogens and detect higher mycorrhizal fungus diversity with the presence of Pinaceae. Under future warming, we can expect feedbacks between fungus composition and plant diversity changes which will affect forest advance, species diversity, and ecosystem stability in arctic regions.