Deep mitochondrial divergence within species may result from cryptic speciation, from phylogeographic isolation or from endosymbiotic bacteria like Wolbachia that manipulate host reproduction. Phengaris butterflies are social parasites that spend most of their life in close relationship with ants. Previously, cryptic speciation has been hypothesised for two Phengaris species based on divergent mtDNA sequences. Since Phengaris species are highly endangered, the existence of cryptic species would have drastic consequences for conservation and management. We tested for cryptic speciation and alternative scenarios in P. teleius and P. nausithous based on a comprehensive sample across their Palaearctic ranges using COI gene sequences, nuclear microsatellites and tests for Wolbachia. In both species a deep mitochondrial split occurring 0.65-1.97 myrs ago was observed that did not correspond with microsatellite data but was concordant with Wolbachia infection. Haplotypes previously attributed to cryptic species were part of the Wolbachia-infected clades. In both species remaining phylogeographic structure was largely consistent between mitochondrial and nuclear genomes. In P. teleius several mitochondrial and nuclear groups were observed in East Asia while a single haplogroup and nuclear cluster prevailed across continental Eurasia. Neutrality tests suggested rapid demographic expansion into that area. In contrast, P. nausithous had several mitochondrial and nuclear groups in Europe, suggesting a complex phylogeographic history in the western part of the species range. We conclude that deep intraspecific divergences found in DNA barcode studies do not necessarily need to represent cryptic speciation but instead can be due to both infection by Wolbachia and phylogeographic structure.