Non-native plants often alter environments they invade, favouring their own performance through positive feedbacks. Plant-soil interactions represent one such mechanism, but their complexity (e.g. invader-induced changes in soil nutrients, microbial communities, etc.) makes inferences of the precise mechanisms that benefit invaders difficult. Here we aimed to determine: 1) whether invasion by Australian acacias (genus Acacia L.) changes nitrogen-fixing soil microbial community diversity and structure, and 2) the importance of available rhizobial partners and overall invader-induced soil changes as significant facilitators of acacia performance. We sampled soils from various invaded and nearby uninvaded areas in South Africa’s Core Cape Subregion and, using next generation sequencing data, compared nitrogen-fixing soil microbial communities between invaded and univaded soils. We then determined the relative importance of soil status (invaded vs. uninvaded), in conjunction with the rhizobial addition, to the performance of invasive acacias under common garden conditions. Next generation sequencing data revealed that invaded soils generally harboured lower nitrogen-fixing microbial diversity and were compositionally more homogenous, compared to uninvaded soils. Bradyrhizobium strains, the most common known rhizobial associate of acacias, were more abundant in invaded than uninvaded sites. Our greenhouse experiments found significantly reduced growth performances of acacias in uninvaded relative to invaded soils for most species by site comparisons, and almost no influence of additional rhizobial inoculum However, the overall relationship between nodulation and growth kinetics was much steeper for plants grown in uninvaded soils compared to invaded soils. Despite invasive acacias homogenising nitrogen-fixing microbial community composition and reducing diversity, it appears that mutualist availability poses no significant barrier to acacia establishment. Although acacia-induced changes to soil conditions enhance plant performance, our successful nodulation seems important to early growth performance of acacias when encountering novel soil conditions. We provide evidence that invasions by Australian acacias affect the diversity and structure of soil rhizobial communities. Although overall soil changes benefit their performance independent of rhizobia addition, forming successful mutualistic interactions is critical during the establishment phase under novel environmental conditions. Taken together, our results indicate that interactions between soil abiotic and biotic conditions work in concert to enhance invader performance though positive feedbacks.