The amphipod Dikerogammarus villosus has colonized most of the European main inland water bodies in less than 20 years, having deteriorating effect on the local benthic communities. Our aim was to reveal the species phylogeography in the native Black Sea area, to define the source populations for the colonization routes in continental Europe and for the newly established UK populations. We tested for the loss of genetic diversity between source and invasive populations as well as along invasion route. We tested also for isolation by distance. Thirty three native and invasive populations were genotyped for mtDNA (COI, 16S) and seven polymorphic nuclear microsatellites to assess cryptic diversity (presence of deeply divergent lineages), historical demography, level of diversity within lineage (e.g., number of alleles), and population structure. A wide range of methods was used, including minimum spanning network, molecular clock, Bayesian clustering and Mantel test. Our results identified that sea level and salinity changes during Pleistocene impacted the species phylogeography in the Black Sea native region with four differentiated populations inhabiting, respectively, the Dnieper, Dniester, Danube deltas and Durungol liman. The invasion of continental Europe is associated with two sources, i.e., the Danube and Dnieper deltas, which gave origin to two independent invasion routes (Western and Eastern) for which no loss of diversity and no isolation by distance were observed. The UK population has originated in the Western Route and, despite very recent colonization, no drastic loss of diversity was observed. The results show that the invasion of the killer shrimp is not associated with the costs of loosing genetic diversity, which may contribute to the success of this invader in the newly colonized areas. Additionally, while it has not yet occurred, it might be expected that future interbreeding between the genetically diversified populations from two independent invasion routes will potentially even enhance this success.