Knowing the phylogeographic structure of invasive species is important for understanding the underlying processes of invasion. The micromoth Phyllonorycter issikii, whose larvae damage leaves of lime trees Tilia spp., was only known from East Asia. In the last three decades, it has been recorded in most of Europe, Western Russia and Siberia. We used the mitochondrial cytochrome c oxidase subunit I (COI) gene region to compare the genetic variability of P. issikii populations between these different regions. Additionally, we sequenced two nuclear genes (28S rRNA and Histone 3) and run morphometric analysis of male genitalia to probe for the existence of cryptic species. The analysis of COI data of 377 insect specimens collected in 16 countries across the Palearctic revealed the presence of two different lineages: P. issikii and a putative new cryptic Phyllonorycter species distributed in the Russian Far East and Japan. In P. issikii, we identified 31 haplotypes among which 23 were detected in the invaded area (Europe) and 10 were found in its putative native range in East Asia (Russian Far East, Japan, South Korea and China), with only two common haplotypes. The high number of haplotypes found in the invaded area suggest a possible scenario of multiple introductions. One haplotype H1 was dominant (119 individuals, 67.2%), not only throughout its expanding range in Europe and Siberia but, intriguingly, also in 96% of individuals originating from Japan. We detected eight unique haplotypes of P. issikii in East Asia. Five of them were exclusively found in the Russian Far East representing 95% of individuals from that area. The putative new cryptic Phyllonorycter species showed differences from P. issikii for the three studied genes. However, both species are morphologically undistinguishable. They occur in sympatry on the same host plants in Japan (Sendai) and the Russian Far East (Primorsky krai) without evidence of admixture.