The phylogenetic relationships of the subgenera Polyommatus and Plebicula, within the Palaearctic butterfly genus Polyommatus, were inferred from a combined analysis of the nuclear marker ITS2 and the barcoding section of the mitochondrial gene COI. Eight major clades were recovered within Polyommatus s. l., which correspond closely to subgenera based on traditional systematics and are of late Pliocene to early Pleistocene origin. Extraordinary chromosomal evolution occurred independently in three of these clades. The disputed position of several species formerly placed in the subgenus Plebicula is clarified. A group of Central Asian species (Bryna) was recovered as a monophyletic clade within Polyommatus s. str. The Kurdistanian endemic P. buzulmavi appears as a sister species to P. icarus. P. celina replaces P. icarus in NW Africa and the Canary Islands, and split from the last common ancestor with P. icarus back in the early Pleistocene.