Alien invaders are among us. It’s true! Every day, foreign plants and animals are turning up in new places. Some of these non-native species do extremely well and out-compete native species. They can cause environmental and economic harm. If they do so, we call them “invasive species”. Fortunately, not all non-native species are invasive. But what makes some species successful invaders and some not? Could beneficial partners be helping out? To find the answer, we studied some invasive legumes (plants in the bean and pea family) and their rhizobial partners. Rhizobia are beneficial bacteria located in legumes’ roots. We found that invasive species can work with a broad variety of rhizobia under greenhouse conditions. However, native and invasive legumes in the wild hosted different types of rhizobia. To our surprise, invasive species had rhizobia similar to the ones in their native land. The question now becomes – where did they get these familiar rhizobia? Could it be a co-invasion?