Phylogeographic studies are often focused on temperate European species with relict footholds in the Mediterranean region. Past climatic oscillations usually induced range contractions and expansions from refugial areas located in southern Europe, and spatial distribution of genetic diversity show that northward expansions were usually pioneer-like. Actually, few studies have focused on circum-Mediterranean species, which probably were not influenced in the same way by climatic oscillations. We present the phylogeography of the bark beetle Tomicus destruens, which is restricted to the whole Mediterranean basin and the Atlantic coasts of North Africa and Portugal. We systematically sequenced 617 bp of the mitochondrial genes COI and COII for 42 populations (N = 219). Analysis revealed 53 haplotypes geographically structured in two clades, namely eastern and western clades, that diverged during the Pleistocene. A contact zone was identified along the Adriatic coast of Italy. Interestingly, we found contrasting levels of genetic structure within each clade. The eastern group was characterized by a significant phylogeographic pattern and low levels of gene flow, whereas the western group barely showed a spatial structure in haplotype distribution. Moreover, the main pine hosts were different between groups, with the Aleppo-brutia complex in the east and the maritime pine in the west. Potential roles of host species, climatic parameters and geographical barriers are discussed and the phylogeographic patterns are compared to classical models of postglacial recolonization in Europe.