Fertility is arguably a very important economic trait in dairy cattle. Genomic prediction for cow fertility has received much attention in the last decade, whereas bull fertility has been largely overlooked. As such, the goal of this study was to investigate the feasibility of genomic prediction of service sire fertility in Holstein and Jersey dairy cattle. Sire conception rate (SCR) was used as a measured of sire fertility. The data set consisted of 11.5k Holstein and 1.5k Jersey bulls with SCR records and genome-wide single nucleotide polymorphism (SNP) data (300k SNPs for Holstein, 96k SNPs for Jersey). Analyses included the use of alternative linear kernel-based models. Predictive ability was evaluated using 5-fold cross-validation with 10 replicates. The entire set of SNPs exhibited predictive correlations of 0.34 and 0.29 for Holsteins and Jerseys, respectively. For Holsteins, 5 SNPs previously found to have marked dominance effects were fitted as fixed effects, increasing the predictive correlation to 0.40. In addition, promising results were found using functional genomic information (e.g., missense or 5′UTR SNP markers) with predictive correlations between 0.29 and 0.33. For Jerseys, adding the entire Holstein population to the training set did not improve model predictive ability. Overall, our findings are very promising and suggest that genomic prediction of dairy bull fertility is feasible. Note that if we divide the estimated predictive correlations by the square root of SCR heritability, we get predictive accuracies up to 0.73. These accuracy values are higher than those obtained for some traits currently evaluated in US dairy cattle; for example, calving ease and some health traits. Our research is the foundation for the development of novel genomic strategies that help the dairy industry make accurate genome-guided decisions, such as early culling of predicted subfertile bull calves.