Sudanese honeybee populations are surrounded by a suite of various subspecies with different mitochondrial haplotypes, including the O-lineage in the north (Egypt), the Y-lineage in the east (Ethiopia) and the A-lineage in the south and west. Using Dra I analyses and the partial sequence of the tRNAleu COII region of 75 sampled colonies throughout Sudan, we never found the Y-lineage in Sudanese honeybees but instead seven different haplotypes from the A-, O-, and C-lineage (A(1), A(4), A(8), A(13), O-1', O-1 and C-2) suggesting that the Y-lineage is not common to Sudan. The mitochondrial haplotypes co-segregated with the highly diverse ecosystems in Sudan. Honeybees of the wet savannah and forest ecosystems showed the A-lineage, identical to A. m. adansonii and A. m. scutellata. The honeybees in the desert, semi desert, and dry savannah of Sudan have the O-lineage, similar to A. m. lamarckii and A. m. syriaca. Haplotype C-2 was found in apiaries with imported stock (A. m. carnica). This reclassification of the honeybees from Sudan has consequences for the interpretation of the biogeography of A. mellifera in the Maghreb and Mashriq regions.