Genetic parentage studies of socially monogamous birds reveal a widespread prevalence of extra-pair paternity. Variation in extra-pair paternity among individuals may depend on how different individuals benefit from extra-pair fertilisations and on the opportunity to pursue extra-pair copulations. A long-term study of sand martins (Riparia riparia) in Hungary allowed us to examine patterns of extra-pair fertilisations in a large colony of over 3,000 breeding pairs with many known age individuals. We used multi-locus DNA fingerprinting to determine whether extra-pair fertilisations occur when females are paired to (1) presumably low quality mates, or (2) genetically similar or dissimilar mates, and whether extra-pair fertilisations result in offspring of higher quality. Extra-paternal young were found in 38% of 47 broods and comprised 19% of 190 offspring. Males that lost paternity did not differ significantly from others in age or body condition. Social mates of broods containing extra-pair offspring did not differ in genetic similarity from pairs without extra-pair offspring. Furthermore, there was no significant difference in body condition between extra-pair young and their maternal half-siblings. We were unable to assign paternity and therefore cannot exclude the possibility that extra-pair males differed from the within-pair males they cuckolded, in age, body condition or genetic similarity with the female. We found a positive relationship between paternity losses and breeding density, suggesting that low breeding density may constrain opportunities for seeking extra-pair copulations.