The frequency of extra-pair paternity (EPP) in socially monogamous birds varies substantially between and within species, but ecological drivers of this variation remain poorly understood. Habitat configuration could influence EPP by moderating access to extra-pair mates, because species occupying territories in a clustered ‘honeycomb’ configuration have a larger pool of potential extra-group mates in their immediate neighbourhood than those living in linearly arranged territories (e.g. along narrow strips of riparian or fragmented habitat). We exploited variation in the spatial arrangement of territories due to anthropogenic modification of habitat of the cooperatively breeding superb fairy-wren Malurus cyaneus to test whether habitat configuration influenced the frequency of EPP. In this species, most paternity is obtained by males outside the social group (extra-group paternity, EGP). We found that the frequency of EGP among groups living in linear strips of roadside vegetation (41% of 44 offspring) was lower than it was for groups living in clustered territories within continuous habitat (59% of 70 offspring). Differences in group size and pair relatedness did not explain differences in EGP associated with territory configuration, though the frequency of EGP was negatively correlated with pair relatedness. Our finding suggests that territory configuration can influence rates of EGP and that anthropogenic habitat fragmentation has the potential to limit access to extra-pair mates, affecting mating systems and ultimately fitness.