During the Last Glacial Maximum in the Northern Hemisphere, expanding ice sheets forced a large number of plants, including trees, to retreat from their primary distribution areas. Many host-associated herbivores migrated along with their host plants. Long-lasting geographic isolation between glacial refugia could have been led to the allopatric speciation in separated populations. Here, we have studied whether the migration history of the Norway spruce Picea abies in Quaternary has affected its host-associated herbivorous beetle-Monochamus sartor. By using microsatellite markers accompanied by the geometric morphometrics analysis of wing venation, we have revealed the clear geographic structure of M. sartor in Eurasia, encompassing two main clusters: southern (Alpine-Carpathian) and eastern (including northeastern Europe and Asia), which reflects the northern and southern ecotypes of its host. The two beetles' lineages probably diverged during the Pleniglacial (57,000-15,000 BC) when their host tree species was undergoing significant range fragmentation and experienced secondary contact during post-glacial recolonization of spruce in the Holocene. A secondary contact of divergent lineages of M. sartor has resulted in the formation of the hybrid zone in northeastern Europe. Our findings suggest that the climatic oscillations during the Pleistocene have driven an insect-plant co-evolutionary process, and have contributed to the formation of the unique biodiversity of Europe.