Organic matter deposited in ancient, ice-rich permafrost sediments is vulnerable to climate change and may contribute to the future release of greenhouse gases; it is thus important to get a better characterization of the plant organic matter within such sediments. From a Late Quaternary permafrost sediment core from the Buor Khaya Peninsula, we analysed plant-derived sedimentary ancient DNA (sedaDNA) to identify the taxonomic composition of plant organic matter, and undertook palynological analysis to assess the environmental conditions during deposition. Using sedaDNA, we identified 154 taxa and from pollen and non-pollen palynomorphs we identified 83 taxa. In the deposits dated between 54 and 51 kyr BP, sedaDNA records a diverse low-centred polygon plant community including recurring aquatic pond vegetation while from the pollen record we infer terrestrial open-land vegetation with relatively dry environmental conditions at a regional scale. A fluctuating dominance of either terrestrial or swamp and aquatic taxa in both proxies allowed the local hydrological development of the polygon to be traced. In deposits dated between 11.4 and 9.7 kyr BP (13.4–11.1 cal kyr BP), sedaDNA shows a taxonomic turnover to moist shrub tundra and a lower taxonomic richness compared to the older samples. Pollen also records a shrub tundra community, mostly seen as changes in relative proportions of the most dominant taxa, while a decrease in taxonomic richness was less pronounced compared to sedaDNA. Our results show the advantages of using sedaDNA in combination with palynological analyses when macrofossils are rarely preserved. The high resolution of the sedaDNA record provides a detailed picture of the taxonomic composition of plant-derived organic matter throughout the core, and palynological analyses prove valuable by allowing for inferences of regional environmental conditions.