The genetic variability and population structure of introduced species in their native range are potentially important determinants of their invasion success, yet data on native populations are often poorly represented in relevant studies. Consequently, to determine the contribution of genetic structuring in the native range of topmouth gudgeon Pseudorasbora parva to their high invasion success in Europe, we used a dataset comprising of 19 native and 11 non-native populations. A total of 666 samples were analysed at 9 polymorphic microsatellite loci and sequenced for 597 bp of mitochondrial DNA. The analysis revealed three distinct lineages in the native range, of which two haplogroups were prevalent in China (100%), with a general split around the Qinling Mountains. Dating of both haplogroups closely matched past geological events. More recently, its distribution has been influenced by fish movements in aquaculture, resulting in gene flow between previously separated populations in Northern and Southern China. Their phylogeography in Europe indicate as few as two introductions events and two dispersal routes. Microsatellite data revealed native populations had higher genetic diversity than those in the invasive range, a contrast to previous studies on P. parva. This study confirms the importance of extensive sampling in both the native and non-native range of invasive species in evaluating the influence of genetic variability on invasion success.