Smallpox, one of the most devastating human diseases, killed between 300 million and 500 million people in the 20th century alone. We recovered viral sequences from 13 northern European individuals, including 11 dated to ~600-1050 CE, overlapping the Viking Age, and reconstructed near-complete variola virus genomes for four of them. The samples predate the earliest confirmed smallpox cases by ~1000 years, and the sequences reveal a now-extinct sister clade of the modern variola viruses that were in circulation before the eradication of smallpox. We date the most recent common ancestor of variola virus to ~1700 years ago. Distinct patterns of gene inactivation in the four near-complete sequences show that different evolutionary paths of genotypic host adaptation resulted in variola viruses that circulated widely among humans.