Reproductive performance is a critical trait in dairy cattle. Poor reproductive performance leads to prolonged calving intervals, higher culling rates and extra expenses related to multiple inseminations, veterinary treatments and replacements. Genetic gain for improved reproduction through traditional selection is often slow because of low heritability and negative correlations with production traits. Detection of DNA markers associated with improved reproductive performance through genome-wide association studies could lead to genetic gain that is more balanced between fertility and production. Norwegian Red cattle are well suited for such studies, as very large numbers of detailed reproduction records are available. We conducted a genome-wide association study for non-return rate, fertility treatments and retained placenta using almost 1 million records on these traits and 17 343 genome-wide single-nucleotide polymorphisms. Genotyping costs were minimized by genotyping the sires of the cows recorded and by using daughter averages as phenotypes. The genotyped sires were assigned to either a discovery or a validation population. Associations were only considered to be validated if they were significant in both groups. Strong associations were found and validated on chromosomes 1, 5, 8, 9, 11 and 12. Several of these were highly supported by findings in other studies. The most important result was an association for non-return rate in heifers in a region of BTA12 where several associations for milk production traits have previously been found. Subsequent fine-mapping verified the presence of a quantitative trait loci (QTL) having opposing effects on non-return rate and milk production at 18 Mb. The other reproduction QTL did not have pleiotropic effects on milk production, and these are therefore of considerable interest for use in marker-assisted selection.