Western honey bees (Apis mellifera) are one of the most important pollinators of agricultural crops and wild plants. Despite the growth in the availability of sequence data for honey bees, the phylogeny of the species remains a subject of controversy. Most notably, the geographic origin of honey bees is uncertain, as are the relationships among its constituent lineages and subspecies. We aim to infer the evolutionary and biogeographical history of the honey bee from mitochondrial genomes. Here we analyse the full mitochondrial genomes of 18 A. mellifera subspecies, belonging to all major lineages, using a range of gene sampling strategies and inference models to identify factors that may have contributed to the recovery of incongruent results in previous studies. Our analyses support a northern African or Middle Eastern origin of A. mellifera. We show that the previously suggested European and Afrotropical cradles of honey bees are the result of phylogenetic error. Monophyly of the M, C, and O lineages is strongly supported, but the A lineage appears paraphyletic. A. mellifera colonised Europe through at least two pathways, across the Strait of Gibraltar and via Asia Minor.