Despite the diversity of Burkholderia species known to nodulate legumes in introduced and native regions, relatively few taxa have been formally described. For example, the Cape Floristic Region of South Africa is thought to represent one of the major centres of diversity for the rhizobial members of Burkholderia, yet only five species have been described from legumes occurring in this region and numerous are still awaiting taxonomic treatment. Here, we investigated the taxonomic status of 12 South African root-nodulating Burkholderia isolates from native papilionoid legumes (Hypocalyptus coluteoides, H. oxalidifolius, H. sophoroides and Virgilia oroboides). Analysis of four gene regions (16S rRNA, recA, atpD and rpoB) revealed that the isolates represent a genealogically unique and exclusive assemblage within the genus. Its distinctness was supported by all other aspects of the polyphasic approach utilized, including the genome-based criteria DNA−DNA hybridization (≥70.9%) and average nucleotide identities (≥96%). We accordingly propose the name B. kirstenboschensis sp. nov. for this taxon with isolate Kb15T (=LMG 28727T; =SARC 695T) as its type strain. Our data showed that intraspecific genome size differences (≥0.81 Mb) and the occurrence of large DNA regions that are apparently unique to single individuals (16−23% of an isolate's genome) can significantly limit the value of data obtained from DNA−DNA hybridization experiments. Substitution of DNA−DNA hybridization with whole genome sequencing as a prerequisite for the description of Burkholderia species will undoubtedly speed up the pace at which their diversity are documented, especially in hyperdiverse regions such as the Cape Floristic Region.