The sexual swellings of female primates have generated a great deal of interest in evolutionary biology. Two hypotheses recently proposed to elucidate their functional significance argue that maximal swelling size advertises either female fertility within a cycle or female quality across cycles. Published evidence favours the first hypothesis, and further indicates that larger swellings advertise higher fertility between cycles. If so, a male preference for large swellings might evolve, driving females to use swellings as quality indicators, as proposed by the second hypothesis. In this paper, we explore this possibility using a combination of empirical field data and mathematical modelling. We first test and find support for three key predictions of the female-quality hypothesis in wild chacma baboons (Papio ursinus): (i) inter-individual differences in swelling size are maintained across consecutive cycles, (ii) females in better condition have larger swellings and higher reproductive success, and (iii) males preferentially choose females with large swellings. We then develop an individual-based simulation model that indicates that females producing larger swellings can achieve higher mating success even when female-female competition is low and within-female variance in the trait is high. Taken together, our findings show that once sexual swellings have evolved as fertility signals, they might, in certain socio-sexual systems, be further selected to act as quality signals. These results, by reconciling two hypotheses, help to clarify the processes underlying sexual swelling evolution. More generally, our findings suggest that mate choice for direct benefits (fertility) can lead to indirect benefits (good genes).