Females in a variety of species commonly mate with multiple males, and there is evidence that they benefit by producing offspring of higher genetic quality; however, the nature of these genetic benefits is debated. Enhanced offspring survival or quality can result from intrinsic effects of paternal genes---'good genes'--or from interactions between the maternal and paternal genomes--'compatible genes'. Evidence for the latter process is accumulating: matings between relatives lead to decreased reproductive success, and the individual level of inbreeding--measured as average heterozygosity--is a strong fitness predictor. Females should thus benefit from mating with genetically dissimilar males. In many birds, social monogamy restricts mate choice, but females may circumvent this by pursuing extra-pair copulations. Here we show that female blue tits, Parus caeruleus, increase the heterozygosity of their progeny through extra-pair matings. Females thereby produce offspring of higher reproductive value, because less inbred individuals have increased survival chances, a more elaborate male secondary sexual trait (crown colour) and higher reproductive success. The cost of inbreeding may therefore be an important factor driving the evolution of female extra-pair mating.