Aphid–plant interactions depend on genotypes of both organisms, which determine the two-way molecular exchange that leads to compatible or incompatible outcomes. The underlying genes are mostly unknown, making it difficult to predict likelihood of aphid success or host resistance, and hampering crop genetic improvement. Here we screened eight pea aphid clonal genotypes collected from diverse legume hosts, on a species-wide panel of Medicago truncatula (Mt) genotypes. Aphid virulence was measured by survival, fecundity and growth rate, together with scores for chlorosis and necrosis as host response indicators. Outcomes were highly dependent on the specific aphid–host genotype combinations. Only one Mt line was fully resistant against all clones. Aphid-induced host chlorosis and necrosis varied greatly, but correlated with resistance only in a few combinations. Bi-clustering analysis indicated that all aphid clones could be distinguished by their performance profiles across the host genotypes tested, with each clone being genetically differentiated and potentially representing a distinct biotype. Clones originating from Medicago sativa ranged from highly virulent to almost completely avirulent on both Medicago species, indicating that some were well adapted, whereas others were most likely migrants. Comparisons of closely related pairs of Australian Mt genotypes differing in aphid resistance revealed no enhanced resistance to European pea aphid clones. Based on the extensive variation in pea aphid adaptation even on unfamiliar hosts, most likely reflecting multiple biotype-specific gene-for-gene interactions, we conclude that robust defences require an arsenal of appropriate resistance genes.