Understanding patterns of colonisation is important for explaining both the distribution of single species and anticipating how ecosystems may respond to global warming. Insular flora may be especially vulnerable because oceans represent severe dispersal barriers. Here we analyse two lake sediment cores from Iceland for ancient sedimentary DNA to infer patterns of colonisation and Holocene vegetation development. Our cores from lakes Torfdalsvatn and Nykurvatn span the last c. 12,000 cal yr BP and c. 8600 cal yr BP, respectively. With near-centennial resolution, we identified a total of 191 plant taxa, with 152 taxa identified in the sedimentary record of Torfdalsvatn and 172 plant taxa in the sedimentary record of Nykurvatn. The terrestrial vegetation at Torfdalsvatn was initially dominated by bryophytes, arctic herbs such as Saxifraga spp. and grasses. Around 10,100 cal yr BP, a massive immigration of new taxa was observed, and shrubs and dwarf shrubs became common whereas aquatic macrophytes became dominant. At Nykurvatn, the dominant taxa were all present in the earliest samples; shrubs and dwarf shrubs were more abundant at this site than at Torfdalsvatn. There was an overall steep increase both in the local accumulated richness and regional species pool until 8000 cal yr BP, by which time ¾ of all taxa identified had arrived. The period 4500-1000 cal yr BP witnessed the appearance of a a small number of bryophytes, graminoids and forbs that were not recorded in earlier samples. The last millennium, after human settlement of the island (Landnám), is characterised by a sudden disappearance of Juniperus communis, but also reappearance of some high arctic forbs and dwarf shrubs. Notable immigration during the Holocene coincides with periods of increased incidence of sea ice, and we hypothesise that this may have acted as a dispersal vector. Thus, although ongoing climate change might provide a suitable habitat in Iceland for a large range of species only found in the neighbouring regions today, the reduction of sea ice may in fact limit the natural colonisation of new plant species.