A variety of Bartonella species were detected in two species of ticks and three species of fleas collected from marsupial hosts; brush-tailed bettong or woylie (Bettongia penicillata) and western barred bandicoots (Perameles bougainville) and from a rodent host; Rattus fuscipes in Western Australia. Bartonella species were detected using nested-PCR of the gltA gene and the 16S-23S ribosomal internal transcribed spacer region (ITS), and species were characterized using DNA sequencing of the 16S rRNA, gltA, rpoB, ftsZ genes and the ITS region. Bartonella rattaustraliani and B. coopersplainsensis were detected in Ixodes spp. ticks and fleas (Stephanocircus pectinipes) respectively collected from rodents. Two novel Bartonella species were detected from marsupials; Candidatus Bartonella woyliei n. sp. was detected in both fleas (Pygiopsylla hilli) and ticks (Ixodes australiensis) collected from woylies and Candidatus Bartonella bandicootii n. sp. was detected in fleas (Pygiopsylla tunneyi) collected from western barred bandicoots. Concatenated phylogenetic analysis of all 5 loci clarified the marsupial cluster of Bartonella species in Australia and confirmed the species status of these two Bartonella species in ticks and fleas from woylies and western barred bandicoots, which are classified as threatened species and are vulnerable to extinction.