Coevolution between hosts and parasites may promote the maintenance of genetic variation in both antagonists by negative-frequency-dependence if the host-parasite interaction is genotype-specific. Here we tested for specificity in the interaction between parasitoids (Lysiphlebus fabarum) and aphid hosts (Aphis fabae) that are protected by a heritable defensive endosymbiont, the γ-proteobacterium Hamiltonella defensa. Previous studies reported a lack of genotype-specificity between unprotected aphids and parasitoids, but suggested that symbiont-conferred resistance might exhibit a higher degree of specificity. Indeed, in addition to ample variation in host resistance as well as parasitoid infectivity, we found a strong aphid clone-by-parasitoid line interaction on the rates of successful parasitism. This genotype-specificity appears to be mediated by H. defensa, highlighting the important role that endosymbionts can play in host-parasite coevolution.