The Mediterranean Sea and adjoining East Atlantic Ocean host a diverse array of small-sized mussels that predominantly live on sunken, decomposing organic remains. At least two of these, Idas modiolaeformis and Idas simpsoni, are known to engage in gill-associated symbioses; however, the composition, diversity and variability of these symbioses with changing habitat and location is poorly defined. The current study presents bacterial symbiont assemblage data, derived from 454 pyrosequencing carried out on replicate specimens of these two host species, collected across seven sample sites found in three oceanographic regions in the Mediterranean and East Atlantic. The presence of several bacterial OTUs in both the Mediterranean Sea and eastern Atlantic suggests that similar symbiont candidates occur on both sides of the Strait of Gibraltar. The results reveal markedly different symbiotic modes in the two species. Idas modiolaeformis displays high symbiont diversity and flexibility, with strong variation in symbiont composition from the East Mediterranean to the East Atlantic. Idas simpsoni displays low symbiont diversity but high symbiont fidelity, with a single dominant OTU occurring in all specimens analysed. These differences are argued to be a function of the host species, where subtle differences in host evolution, life-history and behaviour could partially explain the observed patterns. The variability in symbiont compositions, particularly in Idas modiolaeformis, is thought to be a function of the nature, context and location of the habitat from which symbiont candidates are sourced.