The South African Fynbos soils are renowned for nitrogen-fixing Burkholderia associated with diverse papilionoid legumes of the tribes Crotalarieae, Hypocalypteae, Indigofereae, Phaseoleae and Podalyrieae. However, despite numerous rhizobial studies in the region, the symbiotic diversity of Burkholderia has not been investigated in relation to a specific host legume and its geographical provenance. This study analyzed the diversity of nodulating strains of Burkholderia from the legume species Podalyria calyptrata. Diverse lineages were detected that proved to be closely related to Burkholderia taxa, originating from hosts in other legume tribes. By analyzing the genetic variation of chromosomal (recA) and nodulation (nodA) sequence data in relation to the sampling sites we assessed the geographical distribution patterns of the P. calyptrata symbionts. Although we found a degree of genetically differentiated rhizobial populations, a correlation between genetic (recA and nodA) and geographic distances among populations was not observed, suggesting high rates of dispersal and rhizobial colonization within Fynbos soils.