It has recently become apparent that females of many species of birds often copulate with, and produce young sired by, males other than their social mates. Understanding the adaptive significance of this behaviour requires knowing whether extra-pair matings entail any cost to females. We investigated nest success relative to paternity in red-winged blackbirds (Agelaius phoeniceus) over 5 years and found that nest success declined as the proportion of nestlings that was sired by extra-pair males increased. Nest defence against potential predators is the principal form of paternal care in this population. Males defended nests less vigorously when they contained nestlings sired by other males, suggesting that the lower success of those nests was a consequence of reduced paternal care. Nests with extra-pair young were more successful when the true father was a local resident, suggesting that resident males may defend other males' nests if they have sired some of the young. Our results indicate that females must relize substantial improvement in offspring fitness if they are to compensate for the cost of extra-pair fertilizations.