Since the discovery of Paraburkholderia tuberum, an indigenous South African species and one of the first beta-rhizobia described, several other South African rhizobial Paraburkholderia species have been recognized. In this study, we investigate the taxonomic status of 31 rhizobial isolates recovered from the root nodules of diverse South African legume hosts in the Cape Floristic Region, which were initially identified as P. tuberum or P. tuberum-like. These isolates associate with several genera in the Papilionoideae (e.g., Cyclopia, Virgilia, Hypocalyptus, Podalyria and Aspalathus) and with Vachellia karroo from the mimosoid clade. Genealogical concordance analysis was used to assign these isolates to potential species. This was accomplished by identifying unique and consistent clusters across the genealogies inferred from the DNA sequences of six independent housekeeping genes (i.e., atpD, gyrB, gltB, rpoB, acnA, pab and 16S rRNA). The isolates consistently formed two clusters, thus generating two primary species clusters (Clusters A and B). However, Cluster A included P. tuberum STM678T, suggesting that this monophyletic group could be the actual P. tuberum, while the other one is new to science. Tests for several phenotypic and genotypic characteristics were performed to seek further support for these species clusters, where ANI values (>95%) confirmed them as unique taxa. The cluster representing Paraburkholderia tuberum sensu stricto included isolates from multiple host species, while the other one associated with single Podalyria species from which the name Paraburkholderia podalyriae sp. nov. with the type strain WC7.3bT (= SARCC 750T) was derived.