Vestimentiferan tube worms from deep-sea hydrothermal vents and cold-water seeps rely entirely on sulfur-oxidizing bacterial endosymbionts for nutriment. We examined host-symbiont co-evolution by comparing phylogenetic trees from symbiont 16S ribosomal DNA and host mitochondrial COI genes. The endosymbionts comprised two distinct clades, one associated with tube worms from basaltic vent habitats and the other associated with tube worms from sedimented seep-like environments. Within each symbiont clade, 16S rDNA sequences were nearly identical, suggesting that vent vestimentiferans share a single endosymbiont species that is distinct from the seep endosymbiont species. A third endosymbiont type, related to the seep species, was found in a tube worm collected from a whale carcass. Our results are consistent with a horizontal model of symbiont transmission.