Worldwide, most beef breeding herds are naturally mated. As such, the ability to identify and select fertile bulls is critically important for both productivity and genetic improvement. Here, we collected ten fertility-related phenotypes for 6,063 bulls from six tropically adapted breeds. Phenotypes were comprised of four bull conformation traits and six traits directly related to the quality of the bull's semen. We also generated high-density DNA genotypes for all the animals. In total, 680,758 single nucleotide polymorphism (SNP) genotypes were analyzed. The genomic correlation of the same trait observed in different breeds was positive for scrotal circumference and sheath score on most breed comparisons, but close to zero for the percentage of normal sperm, suggesting a divergent genetic background for this trait. We confirmed the importance of a breed being present in the reference population to the generation of accurate genomic estimated breeding values (GEBV) in an across-breed validation scenario. Average GEBV accuracies varied from 0.19 to 0.44 when the breed was not included in the reference population. The range improved to 0.28 to 0.59 when the breed was in the reference population. Variants associated with the gene HDAC4, six genes from the spermatogenesis-associated (SPATA) family of proteins, and 29 transcription factors were identified as candidate genes. Collectively these results enable very early in-life selection for bull fertility traits, supporting genetic improvement strategies currently taking place within tropical beef production systems. This study also improves our understanding of the molecular basis of male fertility in mammals.