Species of the ectomycorrhizal genus Leccinum are generally considered to be host specialists. We determined the phylogenetic relationships between species of Leccinum from Europe and North America based on second internal transcribed spacer (ITS2) and glyceraldehyde 3-phosphate dehydrogenase (Gapdh). We plotted host associations onto the phylogenies using maximum likelihood and parsimony approaches. Resolution of the phylogeny was greater with Gapdh vs ITS2, plus the Gapdh and ITS phylogenies were highly incongruent. In Leccinum the coding region of Gapdh evolved clocklike, allowing the application of a molecular clock for the reconstruction of host specificity. Almost all species of Leccinum are highly host tree specific, except Leccinum aurantiacum, which associates with a broad range of host trees. Maximum likelihood reconstructions of the ancestral host associations show that this taxon evolved from a specialist. Our results indicate episodes of rapid speciation coinciding with or immediately following host switches. We propose a model where host niche contraction through geographic isolation and host niche expansion through ecologically equivalent hosts drive cycles of speciation. The role of host race formation and incipient speciation is discussed.