Extra-pair paternity (EPP) is a widespread and highly variable reproductive phenomenon in birds. We tested the effects of habitat, spatial factors, and timing of breeding on the occurrence of EPP in red-winged blackbirds (Agelaius phoeniceus). We used PCR-amplified microsatellites to assess the paternity of 1479 nestlings from 537 broods on 235 territories over four breeding seasons. Over 4 years, 40% of nestlings were extra-pair. At least 27% of actual sires were non-neighbours, suggesting that males or females interacted over longer distances than in other populations of red-winged blackbirds. The level of EPP was significantly clumped within broods and males but not within females across broods. EPP was negatively related to the area of a male's territory. The spatial proximity of a female's nest to the territory boundary had no effect on total EPP, but tended to increase the probability of an EPP by a nearby male. We found no influence on EPP of the type of habitat on the territory or the level of nesting activity nearby. The time in the season when a nest was started and the synchrony of breeding also had no significant effect on the level of EPP. The age of the male, the age of his neighbours, and the interaction between the two had no effect on total EPP. However, older males were less likely to have an offspring sired by a neighbour on their territory. Males with older neighbours were also less likely to have offspring sired by a neighbour, particularly if they were new territory owners. The high variability in who gained and lost paternity, and the limited impact of spatial and temporal factors influencing it, have some interesting implications for theories seeking to explain mating patterns.