We characterized Apis mellifera in both native and introduced ranges using 1136 single-nucleotide polymorphisms genotyped in 341 individuals. Our results indicate that A. mellifera originated in Africa and expanded into Eurasia at least twice, resulting in populations in eastern and western Europe that are geographically close but genetically distant. A third expansion in the New World has involved the near-replacement of previously introduced "European" honey bees by descendants of more recently introduced A. m. scutellata ("African" or "killer" bees). Our analyses of spatial transects and temporal series in the New World revealed differential replacement of alleles derived from eastern versus western Europe, with admixture evident in all individuals.