The geographical distributions of species associated with European temperate broadleaf forests have been significantly influenced by glacial-interglacial cycles. During glacial periods, these species persisted in Mediterranean and extra-Mediterranean refugia and later, during interglacial periods, expanded northwards. The widespread saproxylic beetle Bolitophagus reticulatus depends closely on European temperate broadleaf forests. It usually develops in the tinder fungus Fomes fomentarius, a major decomposer of broadleaf-wood. We sampled B. reticulatus in sporocarps from European beech (Fagus sylvatica) and Oriental beech (Fagus orientalis) across Europe and the Caucasus region. We analysed mitochondrial gene sequences (cox1, cox2, cob) and 17 microsatellites to reconstruct the geographical distribution of glacial refugia and postglacial recolonization pathways. We found only marginal genetic differentiation of B. reticulatus, except for a significant split between populations of the Caucasus region and Europe. This indicates the existence of past refugia south of the Great Caucasus, and a contact zone with European populations in the Crimean region. Further potential refugia might have been located at the foothills of the Pyrenees and in the Balkan region. Our genetic data suggest a phalanx-wise recolonization of Europe, a reflection of the high mobility of B. reticulatus.