Mutualisms present a challenge for evolutionary theory. How is cooperation maintained in the face of selection for selfishness and cheating? Both theory and data suggest that partner choice, where one species preferentially directs aid to the more cooperative members of the other species, is central to cooperation in many mutualisms. However, the theory has only so far considered the evolutionary effects of partner choice on one of the species in a mutualism in isolation. Here, we investigate the co-evolution of cooperation and choice in a choosy host and its symbiont. Our model reveals that even though choice and cooperation may be initially selected, it will often be unstable. This is because choice reduces variation in the symbiont and, therefore, tends to remove the selective incentive for its own maintenance (a scenario paralleled in the lek paradox in female choice and policing in within-species cooperation). However, we also show that when variability is reintroduced into symbionts each generation, in the form of less cooperative individuals, choice is maintained. This suggests that the presence of cheaters and cheater species in many mutualisms is central to the maintenance of partner choice and, paradoxically, cooperation itself.