The azure-winged magpie (AWM), Cyanopica cyanus, is found in Asia and Iberia. This remarkable disjunct distribution has been variously explained by either the sixteenth-century introduction of birds into Iberia from the Far East, or by the loss of individuals from the central part of their range as a result of Pleistocene glaciations. We have used the mitochondrial control region to undertake a molecular phylogenetic analysis of the AWM, with sequences examined from individuals collected from across the current distribution range and incorporating representatives of all currently defined subspecies. The Western birds are genetically distinct from their Asian congeners and their divergence is basal in the phylogenetic tree. This indicates that the AWM is native to Iberia and not the result of a recent introduction from Asia. In Asia, two major mitochondrial DNA lineages were identified. These correspond to an Inland Asia group and a Pacific Seaboard group, and are separated topographically by the Da Hingan Ling mountains and the Yellow Sea. Molecular clock estimates suggest that these divergences are associated with Pleistocene glaciations. Furthermore, our data do not support the current classification of the AWM into 10 subspecies, as defined based on morphology and geographical distribution.