Selection for higher milk production in United States dairy cattle has been very successful during the past 50 years, however modern lactating dairy cows exhibit a high incidence of subfertility and infertility with a national pregnancy rate of only 15 to 20%. The objective of this study was to identify genomic loci associated with fertility in nulliparous Holstein heifers. Breeding and health records of Holstein heifers (n = 2,333) were analyzed from a commercial heifer raising facility in Southern Idaho. Of these, 1,114 heifers were classified as highly fertile (conceived on first AI service) and 209 were identified as subfertile (did not conceive until after the fourth AI service or culled due to failure to conceive). Blood samples were obtained from the fertility-classified heifers, and DNA was extracted from 497 high fertile and 209 subfertile heifers. The DNA was genotyped with the Illumina Bovine HD Genotyping BeadChip. Quality control consisted of removing SNPs with < 90% call rate, and a MAF < 1% and removing heifers with a genotyping rate < 90%, leaving 575,959 SNPs and 470 fertile and 189 subfertile heifers for analysis. A genome wide association analysis (GWAA) and heritability estimate was conducted with the Efficient Mixed-Model Association expedited (EMMAX) software. This mixed model program empirically estimated a genomic relationship matrix and used it to model the correlation between the fertility phenotypes. Correction for population stratification was done by variance components and resulted in λ_GC = 1.0. The GWAA identified a QTL on BTA4 with a strong association with fertility (P = 2.9 × 10⁻⁹), while loci on BTA1, BTA2, BTA5, BTA6, BTA10, BTA11, BTA18, BTA23, BTA26, BTA27 and BTA28 were identified with a moderate association with fertility (P < 5.0 × 10⁻⁵). The heritability estimate for fertility in Holstein heifers was 0.52. These results indicate that there is ample opportunity to make significant gains in fertility in nulliparous Holstein heifers with genomic selection. This project was supported by Agriculture and Food Research Initiative Competitive Grant no. 2013–68004–20365 from the USDA National Institute of Food and Agriculture.