The genetic landscape of the European flora and fauna was shaped by the ebb and flow of populations with the shifting ice during Quaternary climate cycles. While this has been well demonstrated for lowland species, less is known about high altitude taxa. Here we analyze the phylogeography of the leaf beetle Oreina elongata from 20 populations across the Alps and Apennines. Three mitochondrial and one nuclear region were sequenced in 64 individuals. Within an mtDNA phylogeny, three of seven subspecies are monophyletic. The species is chemically defended and aposematic, with green and blue forms showing geographic variation and unexpected within-population polymorphism. These warning colors show pronounced east-west geographical structure in distribution, but the phylogeography suggests repeated origin and loss. Basal clades come from the central Alps. Ancestors of other clades probably survived across northern Italy and the northern Adriatic, before separation of eastern, southern and western populations and rapid spread through the western Alps. After reviewing calibrated gene-specific substitution rates in the literature, we use partitioned Bayesian coalescent analysis to date our phylogeography. The major clades diverged long before the last glacial maximum, suggesting that O. elongata persisted many glacial cycles within or at the edges of the Alps and Apennines. When analyzing additional barcoding pairwise distances, we find strong evidence to consider O. elongata as a species complex rather than a single species.