Despite decades of research, empirical support for the "compatible genes" and "good genes" hypotheses as explanations for adaptive female extra-pair mating remains discordant. One largely un-tested theoretical prediction that could explain equivocal findings is that mating for compatible genes benefits should reduce selection for good genes. However, this prediction does not consider demographic parameters, such as social structuring, that can indirectly influence extra-pair paternity (EPP) outcomes. Drawing on evidence from a previous study, we re-evaluate this hypothesis whilst considering social structuring in a population of tui, Prosthemadera novaeseelandiae, a socially monogamous passerine. Previous research has found possible evidence for mating for good genes because male ornament size correlates with EPP success in this population. Here, we test whether non-random inbreeding of social-pairs indirectly provides the opportunity to gain compatibility benefits from EPP, and thus whether selection for compatible genes and good genes can operate simultaneously. We found that (1) social mates were more closely related than expected through random mating, (2) extra-pair males (EPMs) were less closely related to females than were the females' within-pair mates, and (3) genetically dissimilar males sired offspring with faster growth rates. These results demonstrate that females gain compatible genes benefits from EPP. However, contrary to the compatible genes hypothesis, females in highly-related pairs did not engage more frequently in extra-pair mating. Together with previous research investigating female mate choice in this population, our findings suggest that social pairings between relatives provide a pathway for females to gain compatible genes benefits whilst engaging in extra-pair mating for good genes. This study provides evidence that some fitness benefits from EPP arise automatically through non-random social mating rather than through direct selection on extra-pair mate choice. We argue that when variance in compatibility benefits is an outcome of population structuring, compatible genes benefits need not be gained at the expense of good genes benefits.