Symbioses between eukaryotes and sulfur-oxidizing (thiotrophic) bacteria have convergently evolved multiple times. Although well described in at least eight classes of metazoan animals, almost nothing is known about the evolution of thiotrophic symbioses in microbial eukaryotes (protists). In this study, we characterized the symbioses between mouthless marine ciliates of the genusKentrophoros, and their thiotrophic bacteria, using comparative sequence analysis and fluorescencein situhybridization. Ciliate small-subunit rRNA sequences were obtained from 17 morphospecies collected in the Mediterranean and Caribbean, and symbiont sequences from 13 of these morphospecies. We discovered a newKentrophorosmorphotype where the symbiont-bearing surface is folded into pouch-like compartments, illustrating the variability of the basic body plan. Phylogenetic analyses revealed that all investigatedKentrophorosbelonged to a single clade, despite the remarkable morphological diversity of these hosts. The symbionts were also monophyletic and belonged to a new clade within the Gammaproteobacteria, with no known cultured representatives. Each host morphospecies had a distinct symbiont phylotype, and statistical analyses revealed significant support for host–symbiont codiversification. Given that these symbioses were collected from two widely separated oceans, our results indicate that symbiotic associations in unicellular hosts can be highly specific and stable over long periods of evolutionary time.