Developing accurate genomic evaluations of fertility for tropical beef cattle must deal with at least two major challenges (i) recording cow fertility traits in extensive production systems on large numbers of cows and (ii) the genomic evaluations should work across the breeds, crossbreds, and composites used in tropical beef production. Here, we assess accuracy of genomic evaluations for a trait which can be collected on a large scale in extensive conditions, corpus luteum score (CLscore), which is 1 if ovarian scanning indicates a heifer has cycled by 600 d and 0 if not, in a multi-breed population. A total of 3,696 heifers, including 979 Brahmans, 914 Droughtmasters, and 1,803 Santa Gertrudis in seven herds across 3-yr cohorts with CLscores, were genotyped for 24,211 SNPs. Genotypes were imputed to 728,785 SNPs. GBLUP and BayesR were used to predict GEBV. Accuracy of GEBV was evaluated with two validation strategies. In the first strategy, the last year cohort of heifers from each herd was used for validation, such that every herd had heifers in both reference and validation populations. In the second validation strategy, each herd in turn was removed in its entirety from the reference population, and was used for validation. For both validation strategies, accuracy of GEBV for single breed and multi-breed reference populations was assessed. For the first validation strategy, accuracy of GEBV ranged from 0.2 for Brahmans to 0.4 for Droughtmasters. Increasing marker density from 24K SNPs to 728K SNPs resulted in a small increase in accuracy, and including multiple-breeds in the reference did not help improve accuracy. These results suggest that provided a herd has animals in the reference population, the accuracy of the GEBV is largely determined by within herd (linkage) information. The situation was very different when entire herds were predicted in the second validation. In this case accuracy of GEBV using only 24K SNPs and only a within breed reference was close to zero for all breeds. Accuracy increased substantially when 728K SNPs, BayesR, and a multi-breed reference were used, from 0.15 for Brahmans to 0.35 for Santa Gertrudis. Given the second validation strategy is more likely to reflect the situation for many herds in tropical beef production (no animals in the reference), genomic evaluations for fertility in tropical beef cattle should be based on high-density markers (728K SNPs) and should be multi-breed.