Insects of the genus Lipoptena are parasitic arthropods with a broad host range. Due to the type of parasitism (hematophagy), their potential role as vectors of pathogens, i.e., Bartonella sp., Anaplasma phagocytophilum, Rickettsia spp., and Borrelia burgdorferi is considered. As the range of their occurrence has been changing dynamically in recent years and infestations of humans have increasingly been reported, these organisms are now the subject of numerous studies. Our research aimed to present the molecular characteristics of Bartonella sp. detected in Lipoptena fortisetosa parasitizing wild cervids in south-eastern Poland. Adults of Lipoptena spp. were collected from carcasses of roe deer and red deer between spring and autumn in 2013. The PCR method was used to detect Bartonella sp. in the insects. We report two new haplotypes of the rpoB gene of Bartonella sp. isolated from L. fortisetosa feeding on wild cervids in south-eastern Poland and the presence of this invasive ectoparasitic species in the studied area since 2013. Phylogenetic analyses of newly obtained Bartonella sp. haplotypes confirmed their unique position on the constructed tree and network topology. The rpoB gene sequences found belonging to lineage B support the view that this phylogenetic lineage represents a novel Bartonella species.