Human parvovirus B19 (B19V) is a ubiquitous human pathogen associated with a number of conditions, such as fifth disease in children and arthritis and arthralgias in adults. B19V is thought to evolve exceptionally rapidly among DNA viruses, with substitution rates previously estimated to be closer to those typical of RNA viruses. On the basis of genetic sequences up to ∼70 years of age, the most recent common ancestor of all B19V has been dated to the early 1800s, and it has been suggested that genotype 1, the most common B19V genotype, only started circulating in the 1960s. Here we present 10 genomes (63.9-99.7% genome coverage) of B19V from dental and skeletal remains of individuals who lived in Eurasia and Greenland from ∼0.5 to ∼6.9 thousand years ago (kya). In a phylogenetic analysis, five of the ancient B19V sequences fall within or basal to the modern genotype 1, and five fall basal to genotype 2, showing a long-term association of B19V with humans. The most recent common ancestor of all B19V is placed ∼12.6 kya, and we find a substitution rate that is an order of magnitude lower than inferred previously. Further, we are able to date the recombination event between genotypes 1 and 3 that formed genotype 2 to ∼5.0-6.8 kya. This study emphasizes the importance of ancient viral sequences for our understanding of virus evolution and phylogenetics.