Stem rust is one of the most devastating diseases of wheat. Widely virulent races of the pathogen in the Ug99 lineage (e.g., TTKSK) are threatening wheat production worldwide; therefore, there is an urgent need to enhance the diversity of resistance genes in the crop. The objectives of this study were to identify new sources of resistance in wheat-alien introgression derivatives from Secale cereale, Leymus mollis, L. racemosus, and Thinopyrum junceiforme, postulate genes conferring the resistance, and verify the postulated genes by use of molecular markers. From seedling tests conducted in the greenhouse, the presence of seven known stem rust resistance genes (Sr7b, Sr8a, Sr9d, Sr10, Sr31, Sr36, and SrSatu) was postulated in the wheat-alien introgression lines. More lines possessed a high level of resistance in the field compared with the number of lines that were resistant at the seedling stage. Three 2R (2D) wheat-rye substitution lines (SLU210, SLU238, and SLU239) seemed likely to possess new genes for resistance to stem rust based on their resistance pattern to 13 different stem rust races but the genes responsible could not be identified. Wheat-rye, wheat-L. racemosus, and wheat-L. mollis substitutions or translocations with single and multiple interchanges of chromosomes, in particular of the B and D chromosomes of wheat, were verified by a combination of genomic in situ hybridization and molecular markers. Thus, the present study identified novel resistance genes originating from different alien introgressions into the wheat genome of the evaluated lines. Such genes may prove useful in enhancing the diversity of stem rust resistance in wheat against widely virulent pathogen races such as those in the Ug99 lineage.