Aim: Studying plant-soil interactions of introduced species in different parts of their global range could assist in managing biological invasions by elucidating the level of host specificity of key mutualists. We assessed the role of the soil microbial community (with an emphasis on symbiotic nitrogen-fixing bacteria, collectively termed rhizobia) in determining cross-continental invasion success of five woody legume species. Location: Australia. Methods: For each species, we compared growth of plants in soils from their native and non-native ranges using a glasshouse study, a soil dilution method (most probable number) and T-RFLP to assess rhizobial abundance and community composition, respectively. Results: Acacia longifolia was the only species that had significantly larger above-ground biomass when grown in soils from its non-native range. Rhizobial abundance was equally high across species and ranges, indicating plants are unlikely to be limited by soil rhizobial abundance in non-native ranges. Acacia cyclops, A. saligna and Paraserianthes lophantha formed associations with different rhizobial communities in non-native vs. native range soils. Acacia longifolia and A. melanoxylon associated with similar rhizobial communities in their native and non-native ranges, suggesting that rhizobia may have been accidentally introduced into their novel range with seeds or seedlings. Main conclusions: Invasive success of these five legume species is not constrained by the abundance of rhizobia in novel ranges for established legume populations, at least within Australia. Although differences in rhizobial community composition were evident between the native and non-native ranges for three of the five species, these were not associated with differences in plant growth. Increased above-ground biomass of A. longifolia when grown in soil from its non-native range suggests that invasive success of this species may be associated with differences in the non-rhizobial components of soil microbial communities in the novel range. This information could assist in management practises by facilitating a more instructive and effective screening for invasiveness.