Parasitoidism refers to a major form of inter-species interactions where parasitoids sterilize and/or kill their hosts typically before hosts reach reproductive age. However, relatively little is known about the evolutionary dynamics of parasitoidism. Here we investigate the spatial patterns of genetic variation of Chinese cordyceps, including both the parasitoidal fungus Ophiocordyceps sinensis and its host insects. We sampled broadly from alpine regions on the Tibetan Plateau and obtained sequences on seven fungal and three insect DNA fragments from each of the 125 samples. Seven and five divergent lineages/cryptic species were identified within the fungus and host insects respectively. Our analyses suggested that O. sinensis and host insects originated at similar geographic regions in southern Tibet/Yunnan, followed by range expansion to their current distributions. Cophylogenetic analyses revealed a complex evolutionary relationship between O. sinensis and its host insects. Significant congruence was found between host and parasite phylogenies and the time estimates of divergence were similar, raising the possibility of the occurrence of cospeciation events, but the incongruences suggested that host shifts were also prevalent. Interestingly, one fungal genotype was broadly distributed, consistent with recent gene flow. In contrast, the high-frequency insect genotypes showed limited geographic distributions. The dominant genotypes from both the fungus and the insect hosts may represent ideal materials from which to develop artificial cultivation of this important Chinese traditional medicine. Our results demonstrate that both historical and contemporary events have played important roles in the phylogeography and evolution of the O. sinensis-ghost moth parasitoidism on the Tibetan Plateau.