When a female is sexually promiscuous, the ejaculates of different males compete for the fertilization of her eggs; the more sperm a male inseminates into a female, the more likely he is to fertilize her eggs. Because sperm production is limited and costly, theory predicts that males will strategically allocate sperm (1) according to female promiscuity, (2) saving some for copulations with new females, and (3) to females producing more and/or better offspring. Whether males allocate sperm in all of these ways is not known, particularly in birds where the collection of natural ejaculates only recently became possible. Here we demonstrate male sperm allocation of unprecedented sophistication in the fowl Gallus gallus. Males show status-dependent sperm investment in females according to the level of female promiscuity; they progressively reduce sperm investment in a particular female but, on encountering a new female, instantaneously increase their sperm investment; and they preferentially allocate sperm to females with large sexual ornaments signalling superior maternal investment. Our results indicate that female promiscuity leads to the evolution of sophisticated male sexual behaviour.