Tuberculosis has profoundly altered the course of human history. Here we examine the evolutionary history of M. tuberculosis, focusing on the distribution of strain diversity in humans (past and present) in order to elucidate phylogenetic relationships, examine signals of adaptation to humans, identify the impact of human demography on their spread, and assess patterns of pathogen exchange through time. We use new methods of DNA extraction, library construction, and targeted enrichment to obtain genetic data from prehistoric samples with characteristic lesions of mycobacterial disease. First, using qPCR and targeted enrichment of five mycobacterial genes, we have assessed mycobacterial preservation in over 140 samples. Second, using array capture, we sequenced the M. tuberculosis genome from three ancient Peruvians dating to ~1000 years ago. Our analyses indicate that M. tuberculosis likely “jumped” from zoonotic sources and became a human pathogen within the last 6,000 years. In addition, our results show that ancient Peruvian strains are distinct from any known human-adapted M. tuberculosis form and are most closely related to strains adapted to sea mammals. Sea mammals, specifically Southern Hemisphere pinnipeds, acquired strains from other animals in Africa, and then within the last 2000 years brought these strains to South America.