In cooperatively breeding superb fairy-wrens (Malurus cyaneus), all males contribute to the feeding and defence of young. Despite the expectation that such paternal care should be directed only to relatives, DNA fingerprinting revealed that most offspring (76%, 138 out of 181) were sired by extra-group males that contributed no care, and that almost all broods (95%, 38 out of 40) contained young sired by extra-group fathers. This is the highest known incidence of cuckoldry. This remarkable mating system is produced by female control of fertilization and consistent preference for certain extra-group male genotypes. This choice leads to the production of sons that also gain extra-group fertilizations. One constraint on the extra-pair mate choice of females is the level of parental assistance received from males. Males living in pairs contribute relatively more parental care and are more likely to gain paternity in one of their broods (85%, 11 out of 13) than dominant males in multi-male cooperative groups (30%, 8 out of 27). In groups helpers compensate for the lower parental assistance of dominant males, so the total feeding rate is similar between pairs and groups. This suggests that females allow males in pairs more paternity to ensure their assistance with parental care. Helpers provide an alternative source of paternal investment, and allow females to express unrestricted mate choice. Mating options for females in other species with female control of fertilization may also reflect a trade-off between acquiring the genes of high-quality males for their offspring and parental care of those offspring.