With the advent of next-generation sequencing technology, the genotyping of clinical Mycobacterium tuberculosis strains went through a major breakup that dramatically improved the field of molecular epidemiology but also revolutionized our deep understanding of the M. tuberculosis complex evolutionary history. The intricate paths of the pathogen and its human host are reflected by a common geographical origin in Africa and strong biogeographical associations that largely reflect the past migration waves out of Africa. This long coevolutionary history is cardinal for our understanding of the host-pathogen dynamic, including past and ongoing demographic components, strains' genetic background, as well as the immune system genetic architecture of the host. Coalescent- and Bayesian-based analyses allowed us to reconstruct population size changes of M. tuberculosis through time, to date the most recent common ancestor and the several phylogenetic lineages. This information will ultimately help us to understand the spread of the Beijing lineage, the rise of multidrug-resistant sublineages, or the fall of others in the light of socioeconomic events, antibiotic programs, or host population densities. If we leave the present and go through the looking glass, thanks to our ability to handle small degraded molecules combined with targeted capture, paleomicrobiology covering the Pleistocene era will possibly unravel lineage replacements, dig out extinct ones, and eventually ask for major revisions of the current model.