Aim: Mutualisms are often disrupted for plants introduced to new ranges, yet many of these plants have managed to obtain effective mutualistic associations in their new ranges. There are two potential pathways for non-native plants to reassemble mutualisms: cointroduction (i.e. familiar associations with cointroduced mutualists) or ecological fitting (i.e. forming or adapting novel associations with resident native mutualists). We assessed the importance of each pathway for mutualist reassembly in four Australian Acacia species (A. baileyana, A. dealbata, A. decurrens and A. melanoxylon) and their associated nitrogen-fixing rhizobial symbionts in two non-native locations. Location: Native ranges of acacias in south-eastern Australia and two non-native ranges in New Zealand and South Africa. Methods: Rhizobia associated with each acacia species in each country were isolated and identified based on DNA sequencing of the housekeeping recA gene and the symbiotic nodA gene. Separate phylogenies were reconstructed for each gene region to infer biogeographic histories of acacia-associated rhizobia. Selected rhizobial strains for each acacia species by country combination were used as inocula in a glasshouse experiment and early growth kinetics and nitrogen fixation efficiency of acacia seedlings were compared between inoculum treatments to determine symbiotic effectiveness. Results: All isolated rhizobial strains belonged to the genus Bradyrhizobium. Phylogenetic analyses revealed almost no country- or species-specific clusters of these strains for either gene region and indicated that most acacia-associated bradyrhizobia in New Zealand and South Africa were cointroduced from Australia. These results were supported by little variation in the growth performances of acacia seedlings, irrespective of inoculum treatment. Main conclusions: This study revealed that cointroduction of Australian acacias and their rhizobia may be more prevalent than previously thought. Additionally, a single rhizobium cointroduction event may be sufficient to facilitate the establishment of effective mutualisms in numerous Acacia species, potentially leading to an invasion meltdown.