This paper follows the dramatic changes in scientific research during the last 20 years regarding the relationship between the Mycobacterium tuberculosis complex and its hosts - bovids and/or humans. Once the M. tuberculosis and Mycobacterium bovis genomes were sequenced, it became obvious that the old story of M. bovis evolving into the human pathogen should be reversed, as M. tuberculosis is more ancestral than M. bovis. Nevertheless, the timescale and geographical origin remained an enigma. In the current study human and cattle bone samples were examined for evidence of tuberculosis from the site of Atlit-Yam in the Eastern Mediterranean, dating from 9250 to 8160 (calibrated) years ago. Strict precautions were used to prevent contamination in the DNA analysis, and independent centers used to confirm authenticity of findings. DNA from five M. tuberculosis genetic loci was detected and had characteristics consistent with extant genetic lineages. High performance liquid chromatography was used as an independent method of verification and it directly detected mycolic acid lipid biomarkers, specific for the M. tuberculosis complex. These, together with pathological changes detected in some of the bones, confirm the presence of the disease in the Levantine populations during the Pre-pottery Neolithic C period, more than 8000 years ago.