Molecular markers can help elucidate how neutral evolutionary forces and introduction history contribute to genetic variation in invaders. We examined genetic diversity, population structure and colonization patterns in the invasive Polygonum cespitosum, a highly selfing, tetraploid Asian annual introduced to North America. We used nine diploidized polymorphic microsatellite markers to study 16 populations in the introduced range (northeastern North America), via the analyses of 516 individuals, and asked the following questions: 1) Do populations have differing levels of within-population genetic diversity? 2) Do populations form distinct genetic clusters? 3) Does population structure reflect either geographic distances or habitat similarities? We found low heterozygosity in all populations, consistent with the selfing mating system of P. cespitosum. Despite the high selfing levels, we found substantial genetic variation within and among P. cespitosum populations, based on the percentage of polymorphic loci, allelic richness, and expected heterozygosity. Inferences from individual assignment tests (Bayesian clustering) and pairwise FST values indicated high among-population differentiation, which indicates that the effects of gene flow are limited relative to those of genetic drift, probably due to the high selfing rates and the limited seed dispersal ability of P. cespitosum. Population structure did not reflect a pattern of isolation by distance nor was it related to habitat similarities. Rather, population structure appears to be the result of the random movement of propagules across the introduced range, possibly associated with human dispersal. Furthermore, the high population differentiation, genetic diversity, and fine-scale genetic structure (populations founded by individuals from different genetic sources) in the introduced range suggest that multiple introductions to this region may have occurred. High genetic diversity may further contribute to the invasive success of P. cespitosum in its introduced range.