Bartonellae bacteria are associated with several re-emerging human diseases. These vector-borne pathogens have a global distribution, yet data on Bartonella prevalence and diversity in the Arabian Peninsula are limited. In this study we assessed the Bartonella infection status of the Baluchistan gerbil (Gerbillus nanus), a species associated with pastoral communities throughout the Middle East region, using a multi-gene PCR screening approach. The results demonstrated that 94 (68.1%) of the 138 gerbils trapped on a monthly basis, over a period of one year, were PCR-positive. Sequencing of the gltA gene region confirmed the presence of four discrete Bartonella lineages (I–IV) and high levels of co-infection (33.0%). Each of the four lineages, varied in overall abundance (7.5%–47.9%) and had discernible seasonal peaks. Bartonella status was significantly correlated with ectoparasite presence, but not with sex, nor with season. Statistical analyses further revealed that co-infected individuals had a significantly higher relative body condition. Multi-locus sequence analysis (MLSA) performed with a concatenated dataset of three genetic loci (gltA, nuoG, and rpoB), 1452 nucleotides (nt) in length confirmed that lineage IV, which occurred in 24 PCR-positive animals (25.5%), is most closely related to zoonotic B. elizabethae. The remaining three lineages (I-III) formed a monophyletic clade which, on the basis of gltA was shown to contain bartonellae from diverse Gerbillinae species from the Middle East, suggestive of a gerbil-associated species complex in this region. Lineage I was identical to a Candidatus B. sanaae strain identified previously in Bushy-tailed jirds (Sekeetamys calurus) from Egypt, wherease MLSA indicate that lineages II and III are novel. The high levels of infection and co-infection, together with the presence of multiple Bartonella lineages indicate that Gerbillus nanus is likely a natural reservoir of Bartonella in the Arabian Peninsula.