Over 760 legume species occur in the ecologically-heterogeneous Core Cape Subregion (CCR) of South Africa. This study tested whether the main symbionts of CCR legumes ( Burkholderia and Mesorhizobium) are phylogenetically structured by altitude, pH and soil types. Rhizobial strains were isolated from field nodules of diverse CCR legumes and sequenced for 16S ribosomic RNA (rRNA), recombinase A ( recA) and N-acyltransferase ( nodA). Phylogenetic analyses were performed using Bayesian and maximum likelihood techniques. Phylogenetic signals were determined using the D statistic for soil types and Pagel’s λ for altitude and pH. Phylogenetic relationships between symbionts of the narrowly-distributed Indigofera superba and those of some widespread CCR legumes were also determined. Results showed that Burkholderia is restricted to acidic soils, while Mesorhizobium occurs in both acidic and alkaline soils. Both genera showed significant phylogenetic clustering for pH and most soil types, but not for altitude. Therefore, pH and soil types influence the distribution of Burkholderia and Mesorhizobium in the CCR. All strains of Indigofera superba were identified as Burkholderia, and they were nested within various clades containing strains from outside its distribution range. It is, therefore, hypothesized that I. superba does not exhibit rhizobial specificity at the intragenic level. Implications for CCR legume distributions are discussed.