Plant breeding programs use multi-environment trial (MET) data to select superior lines, with the ultimate aim of increasing genetic gain. Selection accuracy can be improved with the use of advanced statistical analysis methods that employ informative models for genotype by environment interaction, include information on genetic relatedness and appropriately accommodate within-trial error variation. The gains will only be achieved, however, if the methods are applied to suitable MET datasets. In this paper we present an approach for constructing MET datasets that optimizes the information available for selection decisions. This is based on two new concepts that characterize the structure of a breeding program. The first is that of “contemporary groups,” which are defined to be groups of lines that enter the initial testing stage of the breeding program in the same year. The second is that of “data bands,” which are sequences of trials that correspond to the progression through stages of testing from year to year. MET datasets are then formed by combining bands of data in such a way as to trace the selection histories of lines within contemporary groups. Given a specified dataset, we use the A-optimality criterion from the model-based design literature to quantify the information for any given selection decision. We demonstrate the methods using two motivating examples from a durum and chickpea breeding program. Datasets constructed using contemporary groups and data bands are shown to be superior to other forms, in particular those that relate to a single year alone.