The psychedelic mushroom Psilocybe cubensis is cultivated worldwide for recreational and medicinal use. Described initially from Cuba in 1906, there has been substantial debate about its origin and diversification. The prevailing view is that P. cubensis was inadvertently introduced to the Americas when cattle were introduced to the continent from Africa and Europe (approx. 1500 CE), but that its progenitor was endemic to Africa. We report the discovery of the cryptic species Psilocybe ochraceocentrata, the closest wild relative of P. cubensis from sub-Saharan Africa. DNA sequences from type specimens of all known and accessible African species of Psilocybe, and multi-locus phylogenetic and molecular clock analyses, strongly support recognizing African specimens originally identified as P. cubensis as a new species that last shared a common ancestor with P. cubensis approximately 1.5 million years ago (approx. 710 000 to 2.55 million years ago, 95% highest posterior density), long predating cattle domestication. Both species are associated with large herbivore dung, suggesting coprophily in their common ancestor likely predisposed P. cubensis to its present specialization on domesticated cattle dung. Ecological niche modelling using bioclimatic variables for global records of these species indicates historical habitat suitability for the common ancestor of P. cubensis and P. ochraceocentrata across Africa, Asia and the Americas over the last 3 million years. This discovery sheds light on the wild origins of domesticated P. cubensis and provides new genetic resources for research on psychedelic mushrooms.