In this study, we compiled 84-year worth (1934-2017) of genomic and epidemiological data of foot-and-mouth disease virus (FMDV), and performed comprehensive analyses to determine its early origin and transmission route. We found that recombination is a key feature of FMDV, and that the genomic regions coding for structural and non-structural proteins have markedly different evolutionary histories, and evolve at different rates. Despite all of these differences, analyses of both structural and non-structural protein coding regions consistently suggested that the most recent common ancestor of FMDV could be dated back to the Middle Age, ~ 200 to 300 years earlier than previously thought. The ancestors of the Euro-Asiatic and SAT strains could be dated back to the mid-seventeenth century, and to the mid-fifteenth to mid-sixteenth century, respectively. Our results implicated Mediterranean counties as an early geographical origin of FMDV before spreading to Europe and subsequently to Asia and South America.