Many animals are obligately associated with microbial symbionts that provide essential services such as nutrition or protection against predators. It is assumed that in such obligate associations fidelity between the host and its symbionts must be high to ensure the evolutionary success of the symbiosis. We show here that this is not the case in marine oligochaete worms, despite the fact that they are so dependent on their bacterial symbionts for their nutrition and waste recycling that they have lost their digestive and excretory systems. Our metagenomic analyses of 64 gutless oligochaete species from around the world revealed highly variable levels of fidelity not only across symbiont lineages, but also within symbiont clades. We hypothesize that in gutless oligochaetes, selection within host species for locally adapted and temporally stable symbiont communities leads to varying levels of symbiont fidelity and shuffles the composition of symbiont assemblages across geographic and evolutionary scales.