Abiotic stress tolerance in plants is pivotal to increase yield stability, but its genetic basis is still poorly understood. To gain insight into the genetic architecture of frost tolerance, this work evaluated a large mapping population of 1739 wheat (Triticum aestivum L.) lines and hybrids adapted to Central Europe in field trials in Germany and fingerprinted the lines with a 9000 single-nucleotide polymorphism array. Additive effects prevailed over dominance effects. A two-dimensional genome scan revealed the presence of epistatic effects. Genome-wide association mapping in combination with a robust cross-validation strategy identified one frost tolerance locus with a major effect located on chromosome 5B. This locus was not in linkage disequilibrium with the known frost loci Fr-B1 and Fr-B2. The use of the detected diagnostic markers on chromosome 5B, however, does not allow prediction of frost tolerance with high accuracy. Application of genome-wide selection approaches that take into account also loci with small effect sizes considerably improved prediction of the genetic variation of frost tolerance in wheat. The developed prediction model is valuable for improving frost tolerance because this trait displays a wide variation in occurrence across years and is therefore a difficult target for conventional phenotypic selection.