Although vaccinia virus (VACV) was once used as a vaccine to eradicate smallpox on a worldwide scale, the biological origins of VACV are uncertain, as are the historical relationships between the different strains once used as smallpox vaccines. Here, we sequenced additional VACV strains that either represent relatively pristine examples of old vaccines (e.g., Dryvax, Lister, and Tashkent) or have been subjected to additional laboratory passage (e.g., IHD-W and WR). These genome sequences were compared with those previously reported for other VACVs as well as other orthopoxviruses. These extant VACVs do not always cluster in simple phylogenetic trees that are aligned with the known historical relationships between these strains. Rather, the pattern of deletions suggests that all existing strains likely come from a complex stock of viruses that has been passaged, distributed, and randomly sampled over time, thus obscuring simple historical or geographic links. We examined surviving nonclonal vaccine stocks, like Dryvax, which continue to harbor larger and now rare variants, including one that we have designated "clone DPP25." DPP25 encodes genes not found in most VACV strains, including an ankyrin-F-box protein, a homolog of the variola virus (Bangladesh) B18R gene which we show can be deleted without affecting virulence in mice. We propose a simple common mechanism by which recombination of a larger and hypothetical DPP25-like ancestral strain, combined with selection for retention of critically important genes near the terminal inverted repeat boundaries (vaccinia virus growth factor gene and an interferon alpha/beta receptor homolog), could produce all known VACV variants.