Interspecific hybridization can be a driving force for evolutionary processes during plant invasions, by increasing genetic variation and creating novel gene combinations, thereby promoting genetic differentiation among populations of invasive species in the introduced range. We examined regional genetic structure in the invasive Fallopia complex, consisting of F. japonica var. japonica, F. sachalinensis and their hybrid F. x bohemica, in seven regions in Germany and Switzerland using RAPD analysis and flow cytometry. All individuals identified as F. japonica var. japonica had the same RAPD phenotype, while F. sachalinensis (11 RAPD phenotypes for 11 sampled individuals) and F. x bohemica (24 RAPD phenotypes for 32 sampled individuals) showed high genotypic diversity. Bayesian cluster analysis revealed three distinct genetic clusters. The majority of F. x bohemica individuals were assigned to a unique genetic cluster that differed from those of the parental species, while the other F. x bohemica individuals had different degrees of admixture to the three genetic clusters. At the regional scale, the occurrence of male-fertile F. sachalinensis coincided with the distribution of F. x bohemica plants showing a high percentage of assignment to both parental species, suggesting that they originated from hybridization between the parental species. In contrast, in regions where male-fertile F. sachalinensis were absent, F. x bohemica belonged to the non-admixed genetic group, indicating multiple introductions of hybrids or sexual reproduction among hybrids. We also found regional differentiation in the gene pool of F. x bohemica, with individuals within the same region more similar to each other than to individuals from different regions.