The Iberian honey bee has been one of the most surveyed subspecies for genetic diversity. Yet, previous studies have missed an important component of Iberian honey bee variation harbored by populations inhabiting the Atlantic side of the Iberian Peninsula. Herein, we provide a fuller picture of the Iberian honey bee maternal diversity by revealing 16 novel haplotypes detected in honey bees from Portugal. Of the 16 haplotypes, all of African ancestry, 15 belong to the Atlantic sub-lineage AIII while only one fits the most common sub-lineage AI. This level of new variation is remarkable as it represents a 59% increase in the wide-range African lineage and a 188% in sub-lineage AIII. Our findings further highlight the complexity of the Iberian honey bee diversity patterns and reinforce the importance of this southernmost European territory as a reservoir of Apis mellifera genetic diversity, a resource increasingly important in a rapidly changing and demanding world. © 2012 INRA, DIB and Springer-Verlag, France.