The classification of brown leaf rust fungi (Puccinia recondita complex and allied species) on wheat (Triticum aestivum), rye (Secale cereale), and other grasses in the family Poaceae has experienced a long history of controversy and uncertainty due to the reduced morphological characteristics available for taxonomy and difficulty of conducting interfertility experiments. However, because these are pathogens on important crops, it is important to clarify the species delimitations reflecting the natural lineages. In this study, phylogenetic analyses were conducted with DNA sequence data from the ribosomal DNA internal transcribed spacer region and elongation factor 1-α to elucidate this species complex. Three phylogenetic lineages were recovered within the complex of rye leaf rust fungi, P. recondita sensu stricto, which is congruent with existing classifications based on DNA content, sexual compatibility, and morphological studies. The brown leaf rust fungus on wheat (P. triticina) grouped with the related species P. persistens on Elymus repens and E. intermedia as a strongly supported clade. Collections on other Elymus spp. were separated into six clades. Based on the phylogenetic affinities of nine type specimens and aecial host associations, potential taxonomic names were evaluated for selected lineages.