Aim: Phylogeography of fruit trees is challenging due to recurrent exchanges between domesticated and wild populations. Here we tested the eastern refugium hypothesis (ERH) for the carob tree, Ceratonia siliqua, which supports its natural and domestication origins in the eastern Mediterranean and a feral origin in the west. Location: Mediterranean basin. Taxon: Ceratonia siliqua L., Leguminosae. Methods: A phylogenetic reconstruction based on two nuclear and one plastid sequences was performed to estimate the divergence time between the carob tree and its sister species, Ceratonia oreothauma. Variation from four plastid regions and 17 nuclear microsatellite loci were used to decipher genetic structure in the carob tree and to test coalescent-based models by an Approximate Bayesian computation (ABC) approach. We assessed our hypotheses by examining palaeobotanical records and hindcasting the past distribution of the carob tree at Mid-Holocene, Last Glacial Maximum (LGM) and Last Interglacial (LIG) using species distribution modelling. Results: The split between C. oreothauma and C. siliqua was estimated at 6.4 Ma, and a first divergence within C. siliqua at 1.3 Ma. After a continuous presence since the Oligocene, Ceratonia was rarely found in the fossil record during the Pleistocene but present in the western and the eastern Mediterranean. Plastid and nuclear markers, characterized by low allelic richness, revealed a strong west-east genetic structuring. ABC analyses rejected the ERH. Main conclusions: Our study supports a severe population decline during LIG. The strong west–east divergence and the occurrence of four lineages within C. siliqua provided support for a new hypothesis of multiple domestications of the carob tree from native populations throughout the Mediterranean basin.