<p>Mutualisms with nitrogen-fixing rhizobia have been linked to the invasion success of alien legumes, especially in areas with nutrient poor soils. While generalist alien legumes can potentially form symbioses with a range of resident rhizobia, specialist alien legumes may fail to find compatible symbionts in their new ranges. In some instances, alien legumes have been co-introduced with their co-evolved rhizobia. These co-invading legumes and rhizobia may impact the rhizobium associations of native legumes. We tested this idea in South Africa’s Cape Fynbos where invasive Australian <i>Acacia</i> species (acacias) and their co-introduced <i>Bradyrhizobium</i> symbionts dominate many habitats. We sampled rhizobium symbionts from invasive acacias and native legumes at four paired (invaded vs uninvaded) Cape Fynbos sites. Using DNA sequencing, we obtained data for core (16S rRNA; n = 78) and nodulation (NodA; n = 38) genes to compare symbiont richness and phylogenetic placement between invaded and uninvaded subsites. We found no significant difference in the overall rhizobium strain richness associated with native Cape Fynbos legumes sampled from different invaded and uninvaded&#xa0;subsites. Our phylogenetic analyses revealed that Australian acacias were predominantly nodulated by Australian <i>Bradyrhizobium</i> while native Cape Fynbos legumes were predominantly nodulated by native <i>Paraburkholderia</i> strains, despite the presence of dense invasive acacia thickets. Finally, we identified a possible case of horizontal gene transfer between native strains of <i>Bradyrhizobium</i> and <i>Paraburkholderia</i>. Taken together, our results show the widespread occurrence of Australian <i>Bradyrhizobium</i> in Cape Fynbos soils and reveal that native Cape Fynbos rhizobia can co-exist with these rhizobia. It seems that native Cape Fynbos legumes do not form symbioses with invasive Australian rhizobia despite their widespread occurrence in soils.</p>