Postglacial colonization of high-latitude landscapes by tundra vegetation during the early Holocene is an important case study for understanding possible rates and patterns of plant migration in a rapidly warming world. Fossil pollen in lake sediment has been used for many decades to yield insights into Arctic paleovegetation and postglacial biogeography. However, because pollen can be wind-transported long distances and, in some cases, reworked from older deposits on the landscape, pollen-based vegetation histories can sometimes obscure the true history of plant colonization, particularly in treeless landscapes. In contrast, lacustrine sedimentary ancient DNA (sedaDNA) is sourced locally and is less likely to be adequately preserved through reworking events, thus making it more reliable for determining the precise timing of plant colonization. Here, we present three sedaDNA records from Holocene lake sediment across southern Baffin Island, Arctic Canada, that clarify the timing of postglacial vegetation changes. In particular, DNA from the subarctic shrub Betula (dwarf birch) first appears thousands of years after deglaciation in all three lake catchments, suggesting delayed colonization, in contrast to its strong pollen signal in early postglacial sediments. Although moderate levels of Alnus (alder) pollen characterize early to mid-Holocene lake sediments from the region, sedaDNA suggests that Alnus was probably not present in any of the three lake catchments during the Holocene. In addition, aquatic plant community changes indicated by sedaDNA generally correspond to the timing of early Holocene warmth in the region, highlighting the potential utility of aquatic plant DNA as a qualitative temperature proxy. These records highlight the utility of ancient plant DNA in lake sediment for providing complementary information to traditional proxy records, particularly during periods of relatively rapid ecological or climatic change.