The Asian cyprinid fish, the topmouth gudgeon (Pseudorasbora parva), was introduced into Europe in the 1960s. A highly invasive freshwater fish, it is currently found in at least 32 countries outside its native range. Here we analyse a 700 base pair fragment of the mitochondrial cytochrome b gene to examine different models of colonisation and spread within the invasive range, and to investigate the factors that may have contributed to their invasion success. Haplotype and nucleotide diversity of the introduced populations from continental Europe was higher than that of the native populations, although two recently introduced populations from the British Isles showed low levels of variability. Based on coalescent theory, all introduced and some native populations showed a relative excess of nucleotide diversity compared to haplotype diversity. This suggests that these populations are not in mutation-drift equilibrium, but rather that the relative inflated level of nucleotide diversity is consistent with recent admixture. This study elucidates the colonisation patterns of P. parva in Europe and provides an evolutionary framework of their invasion. It supports the hypothesis that their European colonisation was initiated by their introduction to a single location or small geographic area with subsequent complex pattern of spread including both long distance and stepping-stone dispersal. Furthermore, it was preceded by, or associated with, the admixture of genetically diverse source populations that may have augmented its invasive-potential.