The goal of this work is to study the evolution and the degree of horizontal gene transfer (HGT) within rhizobial genera of both Alpha- (Mesorhizobium, Rhizobium) and Beta (Burkholderia) Proteobacteria, originating from South African Fynbos legumes. By using a phylogenetic approach and comparing multiple chromosomal and symbiosis genes, we revealed conclusive evidence of high degrees of horizontal transfer of nodulation genes among closely related species of both groups of rhizobia, but also among species with distant genetic backgrounds (Rhizobium and Mesorhizobium), underscoring the importance of lateral transfer of symbiosis traits as an important evolutionary force among rhizobia of the Cape Fynbos biome. The extensive exchange of symbiosis genes in the Fynbos is in contrast with a lack of significant events of HGT among Burkholderia symbionts from the South American Cerrado and Caatinga biome. Furthermore, homologous recombination among selected housekeeping genes had a substantial impact on sequence evolution within Burkholderia and Mesorhizobium. Finally, phylogenetic analyses of the non-symbiosis acdS gene in Mesorhizobium, a gene often located on symbiosis islands, revealed distinct relationships compared to the chromosomal and symbiosis genes, suggesting a different evolutionary history and independent events of gene transfer. The observed events of HGT and incongruence between different genes necessitate caution in interpreting topologies from individual data types.