Genetic variation for partner quality in mutualisms is an evolutionary paradox. One possible resolution to this puzzle is that there is a tradeoff between partner quality and other fitness-related traits. Here, we tested whether a susceptibility to parasitism is one such tradeoff in the mutualism between legumes and nitrogen-fixing bacteria (rhizobia). We performed two greenhouse experiments with the legume Medicago truncatula. In the first, we inoculated each plant with the rhizobia Ensifer meliloti and with one of 40 genotypes of the parasitic root-knot nematode Meloidogyne hapla. In the second experiment, we inoculated all plants with rhizobia and half of the plants with a genetically variable population of nematodes. Using the number of nematode galls as a proxy for infection severity, we found that plant genotypes differed in susceptibility to nematode infection, and nematode genotypes differed in infectivity. Second, we showed that there was a genetic correlation between the number of mutualistic structures formed by rhizobia (nodules) and the number of parasitic structures formed by nematodes (galls). Finally, we found that nematodes disrupt the rhizobia mutualism: nematode-infected plants formed fewer nodules and had less nodule biomass than uninfected plants. Our results demonstrate that there is genetic conflict between attracting rhizobia and repelling nematodes in Medicago. If genetic conflict with parasitism is a general feature of mutualism, it could account for the maintenance of genetic variation in partner quality and influence the evolutionary dynamics of positive species interactions.