In nature, the intensity of mate choice (i.e., choosiness) is highly variable within and between sexes. Despite growing empirical evidence of male and/or mutual mate choice, theoretical investigations of the joint evolution of female and male choosiness are few. In addition, previous approaches have often assumed an absence of trade-off between the direct benefits per mating and the lower mating rate that results from being choosy. Here we model the joint evolution of female and male choosiness when it is solely ruled by this fundamental trade-off. We show that this trade-off can generate a diversity of stable combinations of choosiness. Mutual mate choice can evolve only if both females and males exhibit long latency after mating. Furthermore, we show that an increase in choosiness in one sex does not necessarily prevent the evolution of mutual mate choice; the outcome depends on details shaping the trade-off: the life history, the decision rule for mate choice, and how the fecundity of a pair is shaped by the quality of both individuals. Last, we discuss the power of the sensitivity of the relative searching time (i.e., of the proportion of a lifetime spent searching for mates) as a predictor of the joint evolution of choosiness.