Date palm (Phoenix dactylifera L.) is a major fruit crop of arid regions that were domesticated 7,000 y ago in the Near or Middle East. This species is cultivated widely in the Middle East and North Africa, and previous population genetic studies have shown genetic differentiation between these regions. We investigated the evolutionary history of P. dactylifera and its wild relatives by resequencing the genomes of date palm varieties and five of its closest relatives. Our results indicate that the North African population has mixed ancestry with components from Middle Eastern P. dactylifera and Phoenix theophrasti, a wild relative endemic to the Eastern Mediterranean. Introgressive hybridization is supported by tests of admixture, reduced subdivision between North African date palm and P. theophrasti, sharing of haplotypes in introgressed regions, and a population model that incorporates gene flow between these populations. Analysis of ancestry proportions indicates that as much as 18% of the genome of North African varieties can be traced to P. theophrasti and a large percentage of loci in this population are segregating for single-nucleotide polymorphisms (SNPs) that are fixed in P. theophrasti and absent from date palm in the Middle East. We present a survey of Phoenix remains in the archaeobotanical record which supports a late arrival of date palm to North Africa. Our results suggest that hybridization with P. theophrasti was of central importance in the diversification history of the cultivated date palm.