Why do some females menstruate at all? Answering this question has implications for understanding the tight links between reproductive function and organismal immunity. Here we build on the growing evidence that menstruation is the by-product of a "choosy" uterus to (i) make the theoretical case for the idea that female immunity is cyclical in menstruating species, (ii) evaluate the evidence for the menstrual modulation of immunity and health in humans and (iii) speculate on the implications of cyclical female health for female behaviour, male immunity and host-pathogen interactions. We argue that an understanding of females' evolved reproductive system is foundational for both tackling the future challenges of the global women's health agenda and predicting eco-evolutionary dynamics in cyclically reproducing species.