The thermophilous giant centipede Scolopendra cingulata is a voracious terrestrial predator, which uses its modified first leg pair and potent venom to capture prey. The highly variable species is the most common of the genus in Europe, occurring from Portugal in the west to Iran in the east. The northernmost occurrences are in Hungary and Romania, where it abides in small isolated fringe populations. We report the rediscovery of an isolated Austrian population of Scolopendra cingulata with the first explicit specimen records for more than 80 years and provide insights into the evolutionary history of the northernmost populations utilizing fragments of two mitochondrial genes, COI and 16S, comprising 1,155 base pairs. We test the previously proposed hypothesis of a speciation by distance scenario, which argued for a simple range expansion of the species from the southeast, via Romania, Hungary and finally to Austria, based on a comprehensive taxon sampling from seven countries, including the first European mainland samples. We argue that more complex patterns must have shaped the current distribution of S. cingulata and that the Austrian population should be viewed as an important biogeographical relict in a possible microrefugium. The unique haplotype of the Austrian population could constitute an important part of the species genetic diversity and we hope that this discovery will initiate protective measures not only for S. cingulata, but also for its habitat, since microrefugia are likely to host further rare thermophilous species. Furthermore, we take advantage of the unprecedented sampling to provide the first basic insights into the suitability of the COI fragment as a species identifying barcode within the centipede genus Scolopendra.