To date, little has been documented about the microorganisms harboured within Australian native ticks. Recently, our research group identified a Borrelia species related to the Relapsing Fever (RF) group in a single tick removed from a wild echidna (Tachyglossus aculeatus). This present study continued on the investigation into the presence of Borrelia by examining 97 Bothriocroton concolor ticks parasitizing echidnas in New South Wales, Queensland and Victoria, Australia. Nested-PCR assays were conducted using Borrelia-specific primers targeting the housekeeping genes (16S rRNA and flaB). Borrelia-specific 16S rRNA and flaB gene PCR assays identified a novel Borrelia sp., related to the RF and reptile-associated (REP) spirochaetes in 39% of B. concolor ticks in New South Wales and Queensland, but not in Victoria. Thirty-eight B. concolor ticks were positive at the flaB locus and the resulting flaB sequences (407 bp) were 88% and 86% similar to the flaB sequences from Borrelia turcica and Borrelia hermsii, respectively. Of the 38 ticks positive in the flaB assay, 28 were also positive with the longer 16S rRNA gene assay (1.2 kb). Phylogenetic analysis revealed that these 16S rRNA sequences belong to a novel Borrelia sp., which formed a unique monophyletic clade that is similar to, but distinct from RF Borrelia spp. and REP-associated Borrelia spp. Furthermore, the novel Borrelia sp. identified in this study does not belong to the Borrelia burgdorferi sensu lato complex. The zoonotic potential and pathogenic consequences of this novel Borrelia sp. are unknown at the current time.