In order to elucidate the evolutionary process of deep-sea Bathymodiolus mussels, we investigated the phylogenetic relationships of 16 species worldwide by analyzing nucleotide sequences of the mitochondrial COI and ND4 genes. Deep-sea mussels were clustered into three groups by basal trichotomous divergence. The first was composed of four species found in Japanese waters and one species from the Gulf of Mexico, which contain methanotrophic endosymbiotic bacteria. The second included nine species distributed in the West and East Pacific, Indian, and Atlantic Oceans. Members of the second group were trichotomously divided into the Indo-West Pacific, Atlantic, and East Pacific subclusters. The Indo-West Pacific subcluster was composed of three very closely related species with mutual genetic distances at the intraspecific level (av. 0.019 in COI and 0.009 in ND4 relative to av. 0.156 in COI and 0.265 in ND4 among Bathymodiolus species other than Cluster A species), suggesting some gene flow among these species. The third consisted of two West Pacific species. Species in the second and third groups contain mainly thioautotrophic endosymbionts, including some species harboring both methanotrophs and thioautotrophs.