Ecosystem boundaries, such as the Arctic-Boreal treeline, are strongly coupled with climate and were spatially highly dynamic during past glacial-interglacial cycles. Only a few studies cover vegetation changes since the last interglacial, as most of the former landscapes are inundated and difficult to access. Using pollen analysis and sedimentary ancient DNA (sedaDNA) metabarcoding, we reveal vegetation changes on Bol'shoy Lyakhovsky Island since the last interglacial from permafrost sediments. Last interglacial samples depict high levels of floral diversity with the presence of trees (Larix, Picea, Populus) and shrubs (Alnus, Betula, Ribes, Cornus, Saliceae) on the currently treeless island. After the Last Glacial Maximum, Larix re-colonised the island but disappeared along with most shrub taxa. This was probably caused by Holocene sea-level rise, which led to increased oceanic conditions on the island. Additionally, we applied two newly developed larch-specific chloroplast markers to evaluate their potential for tracking past population dynamics from environmental samples. The novel markers were successfully re-sequenced and exhibited two variants of each marker in last interglacial samples. SedaDNA can track vegetation changes as well as genetic changes across geographic space through time and can improve our understanding of past processes that shape modern patterns.