The European velvety tree ant (Liometopum microcephalum), forming large colonies defending territories, has specific habitat requirements and occurs in isolated populations irregularly distributed across its range. Its dispersal is slow and colony numbers have been declining in many areas. We assessed the origin of populations across the species range to reconstruct its distributional and evolutionary history. Three mitochondrial and one nuclear DNA markers were sequenced in 157 specimens collected at 42 sites. We constructed haplotype networks, calculated analysis of molecular variance and performed Bayesian evolutionary analysis with lineage divergence time estimations and ancestral area reconstructions. We found 39 mitochondrial haplotypes, the nuclear marker had no variability. More than one haplotype was found within six colonies. Two groups, the European and the Asian, diverged genetically. Seven clades were delimited based on Bayesian evolutionary analysis: the Levantine, Western Anatolian, Black Sea, Northern, Balkan, Northwestern Balkan and Western. The species arose during the Pliocene and the youngest divergences within European clades occurred during the last glaciation. The Levantine clade is the basal one, the ancestral area of European populations is probably the Pannonian Basin.