Besides egg fertilization, females of many taxa obtain direct fitness benefits from male mates, such as food, protection or paternal care. But males often increase their own fitness by mating with several females, among which they distribute sperm along with the above-mentioned benefits, reducing the benefits to individual females. These diverging interests lead to a conflict in which each female may try to ensure male fidelity and get exclusive access to male-provided benefits. Here, we use a theoretical model to show how a female of an externally fertilizing species may achieve mate fidelity by soliciting copulations at such a rate that the male has insufficient sperm left to increase his fitness with additional females. We show that three alternative condition-dependent evolutionarily stable mating relationships emerge in this scenario, based on whether one mate's preference for mating rate dominates, or the conflict is resolved by what amounts to negotiation. We demonstrate how these outcomes depend on some features of physiology, ecology, and behavior. In particular, a greater reproductive benefit to a female from exclusive access to a male partner-or the occasional tendency of females to withhold eggs during mating-can increase male fidelity; and continuous sperm regeneration rather than an initially-set stock of sperm allows for multiple within-pair mating across all three mating patterns.