Predicting the performance of untested single-cross hybrids through genomic prediction (GP) is highly desirable to increase genetic gain. Here, we evaluate the predictive ability (PA) of novel genomic strategies to predict single-cross maize hybrids using an unbalanced historical dataset of a tropical breeding program. Field data comprised 949 single-cross hybrids evaluated from 2006 to 2013, representing eight breeding cycles. Hybrid genotypes were inferred based on their parents’ genotypes (inbred lines) using single-nucleotide polymorphism markers obtained via genotyping-by-sequencing. GP analyses were fitted using genomic best linear unbiased prediction via a stage-wise approach, considering two distinct cross-validation schemes. Results highlight the importance of taking into account the uncertainty regarding the adjusted means at each step of a stage-wise analysis, due to the highly unbalanced data structure and the expected heterogeneity of variances across years and locations of a commercial breeding program. Further, an increase in the size of the training set was not always advantageous even in the same breeding program. The use of the two cycles preceding predictions achieved optimal PA of untested single-cross hybrids in a forward prediction scenario, which could be used to replace the first step of field screening. Finally, in addition to the practical and theoretical results applied to maize hybrid breeding programs, the stage-wise analysis performed in this study may be applied to any crop historical unbalanced data.