Phylogeography, genetic diversity, and demography of central European populations of two flightless xerothermic weevils, Polydrusus inustus and Centricnemus leucogrammus, were studied based on the polymorphism of three mtDNA genes (COII, CytB, and ND1). Results indicate that these xerothermic beetles may have different origins. P. inustus is a recent migrant as the parthenogenetic form has a low level of genetic diversity and lacks a geographic population structure. This is probably a result of a recent (before the end of last glaciation) expansion and/or present dispersal mediated by humans. On the other hand, C. leucogrammus appears to be a relic species as the populations of this species are much more genetically diverse (six distinct clades) and some of the populations are allopatric and others sympatric. They probably diverged and expanded during the last few glaciations. Genetic discontinuities were detected among localities that are now separated by gaps in the distribution. Boundaries (mountains or farmland) separate the populations into three groups: (1) Moravia and Slovakia, (2) the lower Vistula Valley in northern Poland and (3) south-eastern Poland together with western Ukraine. Evidence for recent gene flow was found only among populations from south-eastern Poland and western Ukraine, and between these two groups. One population from northern Poland was surprisingly related to populations in southern Poland, which may be due to extinction of intermediate populations.