Matsutake are commercially important ectomycorrhizal basidiomycetes in the genus Tricholoma. Despite their importance, the systematics of this species complex have remained elusive and little is known about their origin and biogeography. Using DNA analyses on a worldwide sample of matsutake, we present here the first comprehensive definition of natural groupings in this species complex. We infer patterns of migration and propose Eocene origins for the group in western North America by a transfer from an angiosperm-associated ancestor to an increasingly specialized conifer symbiont. From these origins, matsutake appear to have followed migratory routes parallel to those of coniferous hosts. Patterns of vicariance between eastern North America and eastern Asia are resolved and their origins are suggested to stem from migration through Beringia. Using an analysis of genetic dissimilarity and geographical distance, we reject both the possibility that migration into Europe and Asia occurred through Atlantic bridges and the connection between matsutake populations in the Mahgrebi Mountains and those from Europe. Instead, African and European matsutake appear to be the most recent ends of a westward expansion of the domain of these fungi from North America.