Genetic diversity and the way a species is introduced influence the capacity of populations of invasive species to persist in, and adapt to, their new environment. The diversity of introduced populations affects their evolutionary potential, which is particularly important for species that have invaded a wide range of habitats and climates, such as European gorse, Ulex europaeus. This species originated in the Iberian peninsula and colonised Europe in the Neolithic; over the course of the last two centuries it was introduced to, and has become invasive in, other continents. We characterised neutral genetic diversity and its structure in the native range and in invaded regions. By coupling these results with historical data we have identified the way in which gorse populations were introduced and the consequences of introduction history on genetic diversity. Our study is based on the genotyping of individuals from 18 populations at six microsatellite loci. As Ulex europaeus is an allohexaploid species, we used recently developed tools which take into account genotypic ambiguity. Our results show that genetic diversity in gorse is very high, and mainly contained within populations. We confirm that colonisation occurred in two stages. During the first stage, gorse spread out naturally from Spain towards northern Europe, losing some genetic diversity. During the second stage, gorse was introduced by humans into different regions of the world, from northern Europe. These introductions resulted in the loss of rare alleles, but did not significantly reduce genetic diversity and thus the evolutionary potential of this invasive species.