1. The ability to form effective mutualisms with nitrogen-fixing bacteria (rhizobia) is implicated in the success of introduced leguminous plant species, such as Acacia. While Acacia appear to associate with rhizobia where introduced, there is evidence that the extent of this may limit success during early stages of colonization. 2. We examine three Australian Acacia species that have been introduced to New Zealand and ask whether variation in their ability to form rhizobial associations can explain differences in the degree to which they have established and spread since introduction. 3. In both Australia and New Zealand, we used glasshouse experiments to measure growth and nodulation of Acacia seedlings grown under two soil treatments: soils taken from underneath conspecifics (Host+ soils) and soils taken from the same sites but away from Acacia trees (Host-). We predicted that suitable rhizobia would be widespread in Australia leading to similar growth and nodulation in Host+ and Host- soils. However, we predicted lower growth and nodulation in New Zealand Host- soils, relative to New Zealand Host+ soils, due to limited availability of suitable rhizobia away from established conspecifics. We also predicted that differences between Host+ and Host- soils would be less marked in Acacia that were more widespread in New Zealand. Finally, we examined whether the establishment of one Acacia species might facilitate the establishment of other species by planting seedlings into soils associated with each of the two congeners. 4. As predicted, seedling growth and nodulation were lower in Host- than Host+ soils in New Zealand but there was no significant difference in Australia. In both countries, the difference between Host+ and Host- soils was similar for all three species and in conspecific and congeneric soils. 5. Synthesis. In New Zealand, Acacia seedlings that colonize sites away from established conspecifics or congeners are likely to suffer reduced growth and nodulation, which may limit their ability to establish and spread away from introduction sites. However, this limitation was the same for all three species, implying that interactions with soil biota cannot explain differences in the degree to which these Acacia have spread in New Zealand.