Background: Biological invasions are fundamentally biogeographic processes that occur over large spatial scales. Interactions with soil microbes can have strong impacts on plant invasions, but how these interactions vary among areas where introduced species are highly invasive vs. naturalized is still unknown. In this study, we examined biogeographic variation in plant-soil microbe interactions of a globally invasive weed, Centaurea solstitialis (yellow starthistle). We addressed the following questions (1) Is Centaurea released from natural enemy pressure from soil microbes in introduced regions? and (2) Is variation in plant-soil feedbacks associated with variation in Centaurea's invasive success? Methodology/Principal Findings: We conducted greenhouse experiments using soils and seeds collected from native Eurasian populations and introduced populations spanning North and South America where Centaurea is highly invasive and noninvasive. Soil microbes had pervasive negative effects in all regions, although the magnitude of their effect varied among regions. These patterns were not unequivocally congruent with the enemy release hypothesis. Surprisingly, we also found that Centaurea generated strong negative feedbacks in regions where it is the most invasive, while it generated neutral plant-soil feedbacks where it is noninvasive. Conclusions/Significance: Recent studies have found reduced below-ground enemy attack and more positive plant-soil feedbacks in range-expanding plant populations, but we found increased negative effects of soil microbes in range-expanding Centaurea populations. While such negative feedbacks may limit the long-term persistence of invasive plants, such feedbacks may also contribute to the success of invasions, either by having disproportionately negative impacts on competing species, or by yielding relatively better growth in uncolonized areas that would encourage lateral spread. Enemy release from soil-borne pathogens is not sufficient to explain the success of this weed in such different regions. The biogeographic variation in soil-microbe effects indicates that different mechanisms may operate on this species in different regions, thus establishing geographic mosaics of species interactions that contribute to variation in invasion success.