The level of integration between associated partners can range from ectosymbioses to extracellular and intracellular endosymbioses, and this range has been assumed to reflect a continuum from less intimate to evolutionarily highly stable associations. In this study, we examined the specificity and evolutionary history of marine symbioses in a group of closely related sulphur-oxidizing bacteria, called Candidatus Thiosymbion, that have established ecto- and endosymbioses with two distantly related animal phyla, Nematoda and Annelida. Intriguingly, in the ectosymbiotic associations of stilbonematine nematodes, we observed a high degree of congruence between symbiont and host phylogenies, based on their ribosomal RNA (rRNA) genes. In contrast, for the endosymbioses of gutless phallodriline annelids (oligochaetes), we found only a weak congruence between symbiont and host phylogenies, based on analyses of symbiont 16S rRNA genes and six host genetic markers. The much higher degree of congruence between nematodes and their ectosymbionts compared to those of annelids and their endosymbionts was confirmed by cophylogenetic analyses. These revealed 15 significant codivergence events between stilbonematine nematodes and their ectosymbionts, but only one event between gutless phallodrilines and their endosymbionts. Phylogenetic analyses of 16S rRNA gene sequences from 50 Cand. Thiosymbion species revealed seven well-supported clades that contained both stilbonematine ectosymbionts and phallodriline endosymbionts. This closely coupled evolutionary history of marine ecto- and endosymbionts suggests that switches between symbiotic lifestyles and between the two host phyla occurred multiple times during the evolution of the Cand. Thiosymbion clade, and highlights the remarkable flexibility of these symbiotic bacteria.