Historical geological events and climatic changes are believed to have played important roles in shaping the current distribution of species. However, sympatric species may have responded in different ways to such climatic fluctuations. Here we compared genetic structures of two corvid species, the Azure-winged Magpie Cyanopica cyanus and the Eurasian Magpie Pica pica, both widespread but with different habitat dependence and some aspects of breeding behavior. Three mitochondrial genes and two nuclear introns were used to examine their co-distributed populations in East China and the Iberian Peninsula. Both species showed deep divergences between these two regions that were dated to the late Pliocene/early Pleistocene. In the East Chinese clade of C. cyanus, populations were subdivided between Northeast China and Central China, probably since the early to mid-Pleistocene, and the Central subclade showed a significant pattern of isolation by distance. In contrast, no genetic structure was found in the East China populations of P. pica. We suggest that the different patterns in the two species are at least partly explained by ecological differences between them, especially in habitat preference and perhaps also breeding behavior. These dissimilarities in life history traits might have affected the dispersal and survival abilities of these two species differently during environmental fluctuations.