Biological invasions are a major cause of environmental and economic disruption. While ecological factors are key determinants of their success, the role of genetics has been more challenging to demonstrate. The colonization of Australia by the European rabbit is one of the most iconic and devastating biological invasions in recorded history. Here, we show that despite numerous introductions over a 70-y period, this invasion was triggered by a single release of a few animals that spread thousands of kilometers across the continent. We found genetic support for historical accounts that these were English rabbits imported in 1859 by a settler named Thomas Austin and traced the origin of the invasive population back to his birthplace in England. We also find evidence of additional introductions that established local populations but have not spread geographically. Combining genomic and historical data we show that, contrary to the earlier introductions, which consisted mostly of domestic animals, the invasive rabbits had wild ancestry. In New Zealand and Tasmania, rabbits also became a pest several decades after being introduced. We argue that the common denominator of these invasions was the arrival of a new genotype that was better adapted to the natural environment. These findings demonstrate how the genetic composition of invasive individuals can determine the success of an introduction and provide a mechanism by which multiple introductions can be required for a biological invasion.