Nine Burkholderia cepacia complex (Bcc) bacteria were isolated during environmental surveys for the ecological niche of Burkholderia pseudomallei, the aetiological agent of melioidosis, in the Northern Territory of Australia. They represented two multi-locus sequence analysis-based clusters, referred to as Bcc B and Bcc L. Three additional environmental and clinical Bcc B isolates were identified upon deposition of the sequences in the PubMLST database. Analysis of the concatenated nucleotide sequence divergence levels within both groups (1.4 and 1.9%, respectively) and towards established Bcc species (4.0 and 3.9%, respectively) demonstrated that the two taxa represented novel Bcc species. All 12 isolates were further characterized using 16S rRNA and recA gene sequence analysis, RAPD analysis, DNA base content determination, fatty acid methyl ester analysis and biochemical profiling. Analysis of recA gene sequences revealed a remarkable diversity within each of these taxa, but, together, the results supported the affiliation of the two taxa to the Bcc. Bcc B strains can be differentiated from most other Bcc members by the assimilation of maltose. Bcc L strains can be differentiated from other Bcc members by the absence of assimilation of N-acetylglucosamine. The names Burkholderia stagnalis sp. nov. with type strain LMG 28156(T) ( = CCUG 65686(T)) and Burkholderia territorii sp. nov. with type strain LMG 28158(T) ( = CCUG 65687(T)) are proposed for Bcc B and Bcc L bacteria, respectively.