Abiotic stress experienced by autumn-sown crops during winter is of great economic importance as it can have a severe negative impact on yield. In this study, we investigated the genetic architecture of winter hardiness and frost tolerance in triticale. To this end, we used a large mapping population of 647 DH lines phenotyped for both traits in combination with genome-wide marker data. Employing multiple-line cross QTL mapping, we identified nine main effect QTL for winter hardiness and frost tolerance of which six were overlapping between both traits. Three major QTL were identified on chromosomes 5A, 1B and 5R. In addition, an epistasis scan revealed the contribution of epistasis to the genetic architecture of winter hardiness and frost tolerance in triticale. Taken together, our results show that winter hardiness and frost tolerance are complex traits that can be improved by phenotypic selection, but also that genomic approaches hold potential for a knowledge-based improvement of these important traits in elite triticale germplasm.