Same-sex sexual behavior (SSB) is observed across many animal taxa. Some instances of SSB likely arise from animals mating indiscriminately without regard to their partner's sex. The effectiveness of indiscriminate mating strategies depends on the costs and benefits of mating and distinguishability of the sexes—which depends in turn on evolvable signals of sex. Other factors like population density (which determines the rate of encountering potential mates) and investment roles (i.e., which sex invests more in reproduction) are thought to affect the evolution of same-sex and different-sex mating, but there is no consensus as to the direction of these effects. We develop a new model of adaptive coevolution of sexual signaling and discrimination, explicitly incorporating encounter rate, mating costs, and investment roles. Coevolutionary dynamics lead to two distinct equilibria: one with no sexual signals and indiscriminate mating; the other with perfect signaling and exclusively different-sex sexual behavior. Low-density conditions favor indiscriminate strategies, due to the steep opportunity costs of missing a possible mate. High density can favor either discriminate or indiscriminate strategies, depending on investment roles. By providing theoretical predictions for the effects of encounter rate and investment roles, our model bridges gaps between theoretical and empirical work on SSB.