Arctic shrubification is an observable consequence of climate change, already resulting in ecological shifts and global-scale climate feedbacks including changes in land surface albedo and enhanced evapotranspiration. However, the rate at which shrubs can colonize previously glaciated terrain in a warming world is largely unknown. Reconstructions of past vegetation dynamics in conjunction with climate records can provide critical insights into shrubification rates and controls on plant migration, but paleoenvironmental reconstructions based on pollen may be biased by the influx of exotic pollen to tundra settings. Here, we reconstruct past plant communities using sedimentary ancient DNA (sedaDNA), which has a more local source area than pollen. We additionally reconstruct past temperature variability using bacterial cell membrane lipids (brGDGTs) and an aquatic productivity indicator (biogenic silica) to evaluate the relative timing of postglacial ecological and climate changes at a lake on southern Baffin Island, Arctic Canada. The sedaDNA record tightly constrains the colonization of dwarf birch (Betula, a thermophilous shrub) to 5.9 ± 0.1 ka, ~3 ka after local deglaciation as determined by cosmogenic ¹⁰Be moraine dating and >2 ka later than Betula pollen is recorded in nearby lake sediment. We then assess the paleovegetation history within the context of summer temperature and find that paleotemperatures were highest prior to 6.3 ka, followed by cooling in the centuries preceding Betula establishment. Together, these molecular proxies reveal that Betula colonization lagged peak summer temperatures, suggesting that inefficient dispersal, rather than climate, may have limited Arctic shrub migration in this region. In addition, these data suggest that pollen-based climate reconstructions from high latitudes, which rely heavily on the presence and abundance of pollen from thermophilous taxa like Betula, can be compromised by both exotic pollen fluxes and vegetation migration lags.