A large-scale survey of the Iberian honey bee (Apis mellifera iberiensis) diversity patterns, using sequence data of the tRNAleu-cox2 mitochondrial DNA (mtDNA) region, demonstrates that earlier studies based on the DraI test missed significant components of genetic variation. Based on results from this survey, existing haplotype names were revised and updated following a nomenclature system established earlier and extended herein for the intergenic region. A more complete picture of the complex diversity patterns of IHBs is revealed that includes 164 novel haplotypes, 113 belonging to lineage A and 51 to lineage M and within lineage A and 69 novel haplotypes that belong to sub-lineage AI, 13 to AII, and 31 to AIII. Within lineage M, two novel haplotypes show a striking architecture with features of lineages A and M, which based on sequence comparisons and relationships among haplotypes are seemingly ancestral. These data expand our knowledge of the complex architecture of the tRNAleu-cox2 intergenic region in Apis mellifera and re-emphasizes the importance of Iberia as a source of honey bee mtDNA diversity.