Parasites can be used as unique markers to investigate host evolutionary history, independent of host data. Here we show that modern human head lice, Pediculus humanus, are composed of two ancient lineages, whose origin predates modern Homo sapiens by an order of magnitude (ca. 1.18 million years). One of the two louse lineages has a worldwide distribution and appears to have undergone a population bottleneck ca. 100,000 years ago along with its modern H. sapiens host. Phylogenetic and population genetic data suggest that the other lineage, found only in the New World, has remained isolated from the worldwide lineage for the last 1.18 million years. The ancient divergence between these two lice is contemporaneous with splits among early species of Homo, and cospeciation analyses suggest that the two louse lineages codiverged with a now extinct species of Homo and the lineage leading to modern H. sapiens. If these lice indeed codiverged with their hosts ca. 1.18 million years ago, then a recent host switch from an archaic species of Homo to modern H. sapiens is required to explain the occurrence of both lineages on modern H. sapiens. Such a host switch would require direct physical contact between modern and archaic forms of Homo.