Prior to the present study there was limited knowledge about the genetic basis of plant colonization on the 50-year-old island of Surtsey, South Iceland. The aim here was to compare genetic structure of two contrasting species, Festucarubra (arctic fescue) and Empetrum nigrum (crowberry), which have colonized Surtsey since 1973 and 1993, respectively. Inter-simple sequence repeat (ISSR) markers were used to assess genetic diversity and population structure. Two census periods were compared: 1996-1997 and 2005-2006. Using six ISSR primers, we obtained 103 and 139 discernible DNA fragments from F. rubra and E. nigrum respectively. Although the two species displayed similarly high genetic diversity indices (h = 0.238 and 0.235; I = 0.384and 0.380, respectively), they differed significantly in their genetic profiles. Festuca was genetically structured at the subpopulation level (FST = 0.034, p = 0.007), whereas Empetrum showed a lack of genetic differentiation. A Bayesian STRUCTURE computation further revealed temporal and spatial genetic structure of the species. The early arrival grass F. rubra has expanded from a local genepool. The population was however initially established from different sources, forming a genetic melting pot on Surtsey. On the other hand, the late arrival shrub E. nigrum probably derived from a common source of immigrants.