BACKGROUND: Males from many species are believed to advertise their genetic quality through striking ornaments that attract mates. Yet the connections between signal expression, body condition and the genes associated with individual quality are rarely elucidated. This is particularly problematic for the signals of females in species with conventional sex roles, whose evolutionary significance has received little attention and is poorly understood. Here we explore these questions in the sexual swellings of female primates, which are among the most conspicuous of mammalian sexual signals and highly variable in size, shape and colour. We investigated the relationships between two components of sexual swellings (size and shape), body condition, and genes of the Major Histocompatibility Complex (MHC) in a wild baboon population (Papio ursinus) where males prefer large swellings. RESULTS: Although there was no effect of MHC diversity on the sexual swelling components, one specific MHC supertype (S1) was associated with poor body condition together with swellings of small size and a particular shape. The variation in swelling characteristics linked with the possession of supertype S1 appeared to be partially mediated by body condition and remained detectable when taking into account the possession of other supertypes. CONCLUSIONS: These findings suggest a pathway from immunity genes to sexual signals via physical condition for the first time in females. They further indicate that mechanisms of sexual selection traditionally assigned to males can also operate in females.