Bartonellae are facultative intracellular bacteria and are highly adapted to their mammalian host cell niches. Straw-colored fruit bats (Eidolon helvum) are commonly infected with several bartonella strains. To elucidate the genetic diversity of these bartonella strains, we analyzed 79 bartonella isolates from straw-colored fruit bats in seven countries across Africa (Cameroon, Annobon island of Equatorial Guinea, Ghana, Kenya, Nigeria, Tanzania, and Uganda) using a multi-locus sequencing typing (MLST) approach based on nucleotide sequences of eight loci (ftsZ, gltA, nuoG, ribC, rpoB, ssrA, ITS, and 16S rRNA). The analysis of each locus but ribC demonstrated clustering of the isolates into six genogroups (E1 – E5 and Ew), while ribC was absent in the isolates belonging to the genogroup Ew. In general, grouping of all isolates by each locus was mutually supportive; however, nuoG, gltA, and rpoB showed some incongruity with other loci in several strains, suggesting a possibility of recombination events, which were confirmed by network analyses and recombination/mutation rate ratio (r/m) estimations. The MLST scheme revealed 45 unique sequence types (ST1 – 45) among the analyzed bartonella isolates. Phylogenetic analysis of concatenated sequences supported the discrimination of six phylogenetic lineages (E1 – E5 and Ew) corresponding to separate and unique Bartonella species. One of the defined lineages, Ew, consisted of only two STs (ST1 and ST2), and comprised more than one-quarter of the analyzed isolates, while other lineages contained higher numbers of STs with a smaller number of isolates belonging to each lineage. The low number of allelic polymorphisms of isolates belonging to Ew suggests a more recent origin for this species. Our findings suggest that at least six Bartonella species are associated with straw-colored fruit bats, and that distinct STs can be found across the distribution of this bat species, including in populations of bats which are genetically distinct. Bats, with over 1000 recognized species, represent about 20% of all classified mammalian species worldwide. These mammals have a wide range of ecologies and life-history traits, and are now widely recognized as important reservoirs of many pathogens. Bartonella species have been found distributed in a wide range of mammalian species, including bats. About half of recognized Bartonella species, including one bat-associated species, have been associated with human illness. Previous studies have shown that Bartonella species are extremely diverse, with or without evident specificity to their mammalian hosts. Possessing many unique aspects, bartonellae can serve as a useful biological marker to study how microorganisms have evolved and diversified along with their animal hosts in evolutionary history. In this study, we applied multi-locus sequence typing, or MLST, to study the genetic differences of straw-colored fruit bat (Eidolon helvum)-associated Bartonella species. Our studies suggest Bartonella species have both exchanged genetic materials among species through recombination events and lost genes that are perhaps superfluous to their life cycles, which includes an intracellular stage in mammals.