Rodents and bats are the most diverse mammal group that host Bartonella species. In the Americas, they were described as harboring Bartonella species; however, they were mostly characterized to the genotypic level. We describe here Bartonella isolates obtained from blood samples of one rodent (Peromyscus yucatanicus from San José Pibtuch, Yucatan) and two bat species (Desmodus rotundus from Progreso, and Pteronotus parnellii from Chamela-Cuitzmala) from Mexico. We sequenced and described the genomic features of three Bartonella strains and performed phylogenomic and pangenome analyses to decipher their phylogenetic relationships. The mouse-associated genome was closely related to Bartonella vinsonii. The two bat-associated genomes clustered into a single distinct clade in between lineages 3 and 4, suggesting to be an ancestor of the rodent-associated Bartonella clade (lineage 4). These three genomes showed <95% OrthoANI values compared to any other Bartonella genome, and therefore should be considered as novel species. In addition, our analyses suggest that the B. vinsonii complex should be revised, and all B. vinsonii subspecies need to be renamed and considered as full species. The phylogenomic clustering of the bat-associated Bartonella strains and their virulence factor profile (lack of the Vbh/TraG conjugation system remains of the T4SS) suggest that it should be considered as a new lineage clade (L5) within the Bartonella genus.