The island Surtsey was formed in a volcanic eruption south of Iceland in 1963–1967 and has since then been protected and monitored by scientists. The first two moss species were found on Surtsey as early as 1967 and several new bryophyte species were discovered every year until 1973 when regular sampling ended. Systematic bryophyte inventories in a grid of 100 m × 100 m quadrats were made in 1971 and 1972: the number of observed species doubled, with 36 species found in 1971 and 72 species in 1972. Here we report results from an inventory in 2008, when every other of the grid's quadrats were searched for bryophytes. Despite lower sampling intensity than in 1972, distributional expansion and contraction of earlier colonists was revealed as well as the presence of new colonists. A total of 38 species were discovered, 15 of those were not encountered in 1972 and eight had never been reported from Surtsey before (Bryum elegans, Ceratodon heterophyllus, Didymodon rigidulus, Eurhynchium praelongum, Schistidium confertum, S. papillosum, Tortula hoppeana and T. muralis). Habitat loss due to erosion and reduced thermal activity in combination with successional vegetation changes are likely to have played a significant role in the decline of some bryophyte species which were abundant in 1972 (Leptobryum pyriforme, Schistidium apocarpum coll., Funaria hygrometrica, Philonotis spp., Pohlia spp, Schistidium strictum, Sanionia uncinata) while others have continued to thrive and expand (e.g. Schistidium maritimum, Racomitrium lanuginosum, R. ericoides, R. fasciculare and Bryum argenteum). Some species (especially Bryum spp.) benefit from the formation of new habitats, such as grassland within a gull colony, which was established in 1984. Several newcomers are rarely producing sporophytes on Iceland and are unlikely to have been dispersed by airborne spores. They are more likely to have been introduced to Surtsey by seagulls in the form of vegetative fragments or dispersal agents (Bryum elegans, Didymodon rigidulus, Eurhynchium praelongum, Ceratodon heterophyllus and Ulota phyllantha). The establishment of the gull colony also means that leakage of nutrients from the nesting area is, at least locally, downplaying the relative importance of nitrogen fixation by cyanobacteria growing in bryophyte shoots.