Following its introduction into Europe (EU), the common milkweed (Asclepias syriaca) has been free of most specialist herbivores that are present in its native North American (NA) range, except for the oleander aphid Aphis nerii. We compared EU and NA populations of A. nerii on EU and NA milkweed populations to test the hypothesis that plant–insect interactions differ on the two continents. First, we tested if herbivore performance is higher on EU plants than on NA plants, because the former have escaped most of their herbivores and have perhaps been selected for lower defence levels following introduction. Second, we compared two A. nerii lines (one from each continent) to test whether genotypic differences in the herbivore may influence species interactions in plant–herbivore communities in the context of species introductions. The NA population of A. nerii developed faster, had higher fecundity and attained higher population growth rates than the EU population. There was no overall significant continental difference in aphid resistance between the plants. However, milkweed plants from EU supported higher population growth rates and faster development of the NA line of A. nerii than plants from NA. In contrast, EU aphids showed similar (low) performance across plant populations from both continents. In a second experiment, we examined how chewing herbivores indirectly mediate interactions between milkweeds and aphids, and induced A. syriaca plants from each continent by monarch caterpillars (Danaus plexippus) to compare the resulting changes in plant quality on EU aphid performance. As specialist chewing herbivores of A. syriaca are only present in NA, we expected that plants from the two continents may affect aphid growth in different ways when they are challenged by a specialist chewing herbivore. Caterpillar induction decreased aphid developmental times on NA plants, but not on EU plants, whereas fecundity and population growth rates were unaffected by induction on both plant populations. The results show that genetic variation in the plants as well as in the herbivores can determine the outcome of plant–herbivore interactions.