The Mediterranean Basin represents a Global Biodiversity Hotspot where many organisms show high inter- and intraspecific differentiation. Extant phylogeographic patterns of terrestrial circum-Mediterranean faunas were mainly shaped through Pleistocene range shifts and range fragmentations due to retreat into different glacial refugia. Thus, several extant Mediterranean bird species have diversified by surviving glaciations in different hospitable refugia and subsequently expanded their distribution ranges during the Holocene. Such a scenario was also suggested for the Eurasian Wren (Nannus troglodytes) despite the lack of genetic data for most Mediterranean subspecies. Our phylogenetic multi-locus analysis comprised 18 out of 28 currently accepted subspecies of N. troglodytes, including all but one subspecies which are present in the Mediterranean Basin. The resulting phylogenetic reconstruction dated the onset of the entire Holarctic radiation of three Nannus species to the early Pleistocene. In the Eurasian Wren, two North African subspecies represented separate basal lineages from the Maghreb (N. t. kabylorum) and from the Libyan Cyrenaica (N. t. juniperi), being only distantly related to other Mediterranean populations. Although N. troglodytes appeared to be paraphyletic with respect to the Nearctic Winter Wren (N. hiemalis), respective nodes did not receive strong statistical support. In contrast, paraphyly of the Ibero-Maghrebian taxon N. t. kabylorum was strongly supported. Southern Iberian populations of N. t. kabylorum did not clade with Maghrebian populations of the same subspecies but formed a sister clade to a highly diverse European clade (including nominate N. t. troglodytes and eight further taxa). In accordance with a pattern also found in other birds, Eurasian populations were split into a western clade (Europe, Caucasus) and an eastern clade (Central Asia, Sino-Himalayas, East Asia). This complex phylogeographic pattern revealed cryptic diversification in N. troglodytes, especially in the Iberio-Maghrebian region.