Summary A common empirical observation in mutualistic interactions is the persistence of variation in partner quality and, in particular, the persistence of exploitative phenotypes. For mutualisms between hosts and symbionts, most mutualism theory assumes that exploiters always impose fitness costs on their host. We exposed legume hosts to mutualistic (nitrogen‐fixing) and exploitative (non‐nitrogen‐fixing) symbiotic rhizobia in field conditions, and manipulated the presence or absence of insect herbivory to determine if the costly fitness effects of exploitative rhizobia are context‐dependent. Exploitative rhizobia predictably reduced host fitness when herbivores were excluded. However, insects caused greater damage on hosts associating with mutualistic rhizobia, as a consequence of feeding preferences related to leaf nitrogen content, resulting in the elimination of fitness costs imposed on hosts by exploitative rhizobia. Our experiment shows that herbivory is potentially an important factor in influencing the evolutionary dynamic between legumes and rhizobia. Partner choice and host sanctioning are theoretically predicted to stabilize mutualisms by reducing the frequency of exploitative symbionts. We argue that herbivore pressure may actually weaken selection on choice and sanction mechanisms, thus providing one explanation of why host‐based discrimination mechanisms may not be completely effective in eliminating nonbeneficial partners.