Simulation and empirical studies of genomic selection (GS) show accuracies sufficient to generate rapid annual genetic gains. However, genomic selection shifts the focus from the evaluation of genotypes to the evaluation of alleles. Consequently, new methods should be developed to optimize the use of large multi-environment trials for genomic selection. It also becomes possible to use allelic effect variation between environments to characterize them, which provides a new method to cope with unbalanced phenotypic datasets. Using a two-row elite barley population tested for grain yield across Europe from 2007 to 2010 we compare the genome-wide allele by environment interaction with the genotype by environment interaction. Using the Bayesian Lasso (BL) for the genomic selection model we characterized allele-effect estimates at each test location and identified outlier and relevant mega-environments for genomic selection. We propose a new method that uses the predictive ability of an environment to optimize the composition of the training population derived from the complete dataset. This method does not increase accuracy by subdivision of the environments, but instead identifies less predictive environments to yield a gain in cross-validated accuracy from 0.54 to 0.61. Results suggest that genomic selection methodologies that take into account the environmental sensitivity of marker effects in multi-environment trials are important for optimizing the prediction of breeding values and that the use of allele-effect variation between environments helps to analyzing large unbalanced multi-environment trials.