In cooperative breeders the tension between the opposing forces of kin-selection and kin-competition is at its most severe. Although philopatry facilitates kin-selection, it also increases the risk of inbreeding. When dispersal is limited, extra-pair paternity might be an important mechanism to avoid inbreeding, but evidence for this is equivocal. The red-winged fairy-wren is part of a genus of cooperative breeders with extreme levels of promiscuity and male philopatry, but is unique in that females are also strongly philopatric. Here we test the hypothesis that promiscuity is an important inbreeding avoidance mechanism when both sexes are philopatric. Levels of extra-pair paternity were substantial (70% of broods), but did not arise through females mating with their helpers, but via extra-group mating. Offspring were more likely to be sired by extra-pair males when the social pair was closely related, and these extra-pair males were genetically less similar to the female than the social male, thus inbreeding is avoided through extra-pair mating. Females were consistent in their choice of the extra-pair sire over time and preferred early moulting males. Despite neighbouring males often being close kin, they sired 37% of extra-pair offspring. However, females that gained paternity from neighbours were typically less related to them than females that gained paternity further away. Our study is the first to suggest that mating with both closely-related social partners and neighbours is avoided. Such sophistication in inbreeding avoidance strategies is remarkable, since the extreme levels of promiscuity imply that social context may provide little cue to relatedness.