Solanum elaeagnifolium is a weed of national significance in Australia. However, the genetic diversity of S. elaeagnifolium is poorly understood. Four amplified fragment length polymorphism primer combinations were utilised to investigate the genetic variation and structure of 187 S. elaeagnifolium individuals collected from 94 locations in Australia. High genetic diversity was found, with an average Jaccard's genetic similarity at 0.26. Individuals were assigned to two genetic clusters or considered as admixed according to their membership coefficient value (q) calculated by Bayesian model-based genetic structure analysis. This suggested that Australian S. elaeagnifolium may have originated from two distinct gene pools. These results were further supported by principal co-ordinates analysis. Large spatial groups of individuals assigning to these two gene pools were found in western Victoria and south-western New South Wales (NSW) and northern NSW, which correlated well with the early records of S. elaeagnifolium in both regions. The high genetic diversity found here could add difficulties to effective control of S. elaeagnifolium across regions.