Distinct Burkholderia strains were isolated from soil samples collected in tropical northern Australia (Northern Territory and the Torres Strait Islands, Queensland). Phylogenetic analysis of 16S rRNA and whole genome sequences revealed these strains were distinct from previously described Burkholderia species and assigned them to two novel clades within the B. pseudomallei complex (Bpc). Because average nucleotide identity and digital DNA-DNA hybridization calculations are consistent with these clades representing distinct species, we propose the names Burkholderia mayonis sp. nov. and Burkholderia savannae sp. nov. Strains assigned to B. mayonis sp. nov. include type strain BDU6T (=TSD-80; LMG 29941; ASM152374v2) and BDU8. Strains assigned to B. savannae sp. nov. include type strain MSMB266T (=TSD-82; LMG 29940; ASM152444v2), MSMB852, BDU18, and BDU19. Comparative genomics revealed unique coding regions for both putative species, including clusters of orthologous genes associated with phage. Type strains of both B. mayonis sp. nov. and B. savannae sp. nov. yielded biochemical profiles distinct from each other and from other species in the Bpc, and profiles also varied among strains within B. mayonis sp. nov. and B. savannae sp. nov. Matrix-assisted laser desorption ionization time-of-flight (MLST) analysis revealed a B. savannae sp. nov. cluster separate from other species, whereas B. mayonis sp. nov. strains did not form a distinct cluster. Neither B. mayonis sp. nov. nor B. savannae sp. nov. caused mortality in mice when delivered via the subcutaneous route. The addition of B. mayonis sp. nov. and B. savannae sp. nov. results in a total of eight species currently within the Bpc.