We introduce a complementarity dilemma, a two-player, binary response game in which the playoffs are highest when the two players respond differently. Using the classifier EvA, we determine the evolutionary dynamics and structure of strategies that evolve to play an iterated version of this game, and we relate the results to the evolution of major types of sexual reproduction, particularly simultaneous hermaphroditism. We find that complementarity strategies consistently evolve under a broad range of conditions, but that those most consistent with the simultaneous hermaphroditism can predominate only when a substantial cost of repeatedly adopting the female role is imposed. The cost is analogous to the fecundity reduction to be expected when a single partner must repeatedly produce the eggs in sexual reproduction.