Symbiotic relations and range of host usage are prominent in coral reefs and crucial to the stability of such systems. In order to explain how symbiotic relations are established and evolve, we used sponge-associated barnacles to ask three questions. (1) Does larval settlement on sponge hosts require novel adaptations facilitating symbiosis? (2) How do larvae settle and start life on their hosts? (3) How has this remarkable symbiotic lifestyle involving many barnacle species evolved? We found that the larvae (cyprids) of sponge-associated barnacles show a remarkably high level of interspecific variation compared with other barnacles. We document that variation in larval attachment devices are specifically related to properties of the surface on which they attach and metamorphose. Mapping of the larval and sponge surface features onto a molecular-based phylogeny showed that sponge symbiosis evolved separately at least three times within barnacles, with the same adaptive features being found in all larvae irrespective of phylogenetic relatedness. Furthermore, the metamorphosis of two species proceeded very differently, with one species remaining superficially on the host and developing a set of white calcareous structures, the other embedding itself into the live host tissue almost immediately after settlement. We argue that such a high degree of evolutionary flexibility of barnacle larvae played an important role in the successful evolution of complex symbiotic relationships in both coral reefs and other marine systems.