Paxillus rubicundulus P.D. Orton has been shown to be a complex of at least three ectomycorrhizal taxa strictly associated with alders (Alnus) in Europe, P. rubicundulus s. str., and two undescribed clades. To assess the taxonomic status of these three clades and their phylogenetic relationships, phylogenetic analyses of two independent gene regions (ITS and gpd), combined with macro- and micromorphological comparisons of genetically identified specimens, were carried out. A total of 85 sequences were successfully obtained from basidiomata and alder mycorrhizae collected in France and Algeria and combined with GenBank and UNITE sequences. The phylogenetic results and estimates of genetic diversity confirmed that the three clades are distinct species, often found in sympatry. As a result, P. rubicundulus s. str. was redefined based on the revision of type material, and Paxillus adelphus and Paxillus olivellus are introduced as new Linnaean names. The often used name Paxillus filamentosus is rejected since it could not be applied to any of the new species. The three species are distinguished micromorphologically by spore size and shape. They are widely distributed in Europe, North Africa and western Asia; P. rubicundulus is rare, and all species have a limited host range.