The western honey bee, Apis mellifera, provides critical pollination services to agricultural crops worldwide. However, despite substantial interest and prior investigation, the early evolution and subsequent diversification of this important pollinator remain uncertain. The primary hypotheses place the origin of A. mellifera in either Asia or Africa, with subsequent radiations proceeding from one of these regions. Here, we use two publicly available whole-genome data sets plus newly sequenced genomes and apply multiple population genetic analysis methods to investigate the patterns of ancestry and admixture in native honey bee populations from Europe, Africa, and the Middle East. The combination of these data sets is critical to the analyses, as each contributes samples from geographic locations lacking in the other, thereby producing the most complete set of honey bee populations available to date. We find evidence supporting an origin of A. mellifera in the Middle East or North Eastern Africa, with the A and Y lineages representing the earliest branching lineages. This finding has similarities with multiple contradictory hypotheses and represents a disentangling of genetic relationships, geographic proximity, and secondary contact to produce a more accurate picture of the origins of A. mellifera. We also investigate how previous studies came to their various conclusions based on incomplete sampling of populations, and illustrate the importance of complete sampling in understanding evolutionary processes. These results provide fundamental knowledge about genetic diversity within Old World honey bee populations and offer insight into the complex history of an important pollinator.