Ailanthus altissima is a common tree species of the European non-native flora. In Eastern Austria, Ailanthus has both a long tradition, dating back to the late 18th century, and a high frequency of occurrence. Here, we apply molecular markers from the nuclear and chloroplast DNA in order to study the origin, as well as the clonal and genetic structure of the species in forest stands of this region. Our results indicate a single area of origin for all our study populations from the north-eastern part of the native range, in agreement with historical reports. Within populations, vegetative reproduction has resulted in extensive clonal structures at some sites. Long presence and repeated vegetative recruitment might have led to expansion of clones in areas of early introduction. In addition, limited mate availability may also have promoted vegetative reproduction. Tests for recent bottlenecks were significant in almost all stands, possibly reflecting founder effects since the introduction of Ailanthus in our study area. Among populations, we found a very pronounced and significant genetic structure, which did not follow a spatial pattern. We argue that founder effects due to population establishment with a low number of propagules – whether naturally or artificially – have caused genetic drift and a structured gene pool. The lack of spatial pattern or isolation-by-distance suggests that seed transfer by humans might have been a major factor shaping the genetic variation of Ailanthus in Eastern Austria.