Background. Evidence of multiple genetic criteria of mate choice is accumulating in numerous taxa. In many species, females have been shown to pair with genetically dissimilar mates or with extra-pair partners that are more genetically compatible than their social mates, thereby increasing their offsprings' heterozygosity which often correlates with offspring fitness. While most studies have focused on genetically promiscuous species, few studies have addressed genetically monogamous species, in which mate choice tends to be mutual. Results. Here, we used microsatellite markers to assess individual global heterozygosity and genetic similarity of pairs in a socially and genetically monogamous seabird, the black-legged kittiwake Rissa tridactyla. We found that pairs were more genetically dissimilar than expected by chance. We also identified fitness costs of breeding with genetically similar partners: (i) genetic similarity of pairs was negatively correlated with the number of chicks hatched, and (ii) offspring heterozygosity was positively correlated with growth rate and survival. Conclusion. These findings provide evidence that breeders in a genetically monogamous species may avoid the fitness costs of reproducing with a genetically similar mate. In such species that lack the opportunity to obtain extra-pair fertilizations, mate choice may therefore be under high selective pressure. ?? 2009 Mulard et al; licensee BioMed Central Ltd.