Archeological and genetic evidence suggest that all domestic cats derived from the Near Eastern wildcat (Felis silvestris lybica) and were first domesticated in the Near East around 10,000 years ago. The spread of the domesticated form in Europe occurred much later, primarily mediated by Greek and Phoenician traders and afterward by Romans who introduced cats to Western and Central Europe around 2000 years ago. We investigated mtDNA of Holocene Felis remains and provide evidence of an unexpectedly early presence of cats bearing the Near Eastern wildcat mtDNA haplotypes in Central Europe, being ahead of Roman period by over 2000 years. The appearance of the Near Eastern wildcats in Central Europe coincides with the peak of Neolithic settlement density, moreover most of those cats belonged to the same mtDNA lineages as those domesticated in the Near East. Thus, although we cannot fully exclude that the Near Eastern wildcats appeared in Central Europe as a result of introgression with European wildcat, our findings support the hypothesis that the Near Eastern wildcats spread across Europe together with the first farmers, perhaps as commensal animals. We also found that cats dated to the Neolithic period belonged to different mtDNA lineages than those brought to Central Europe in Roman times, this supports the hypothesis that the gene pool of contemporary European domestic cats might have been established from two different source populations that contributed in different periods.