During a biological invasion, we expect that the expanding front will increasingly become dominated by individuals with better dispersal abilities. Over many generations, selection at the invasion front thus will favour traits that increase dispersal rates. As a result of this process, cane toads (Bufo marinus) are now spreading through tropical Australia about 5-fold faster than in the early years of toad invasion; but how have toads changed to make this happen? Here we present data from radio-tracking of free-ranging cane toads from three populations (spanning a 15-year period of the toads' Australian invasion, and across 1800km). Our data reveal dramatic shifts in behavioural traits (proportion of nights when toads move from their existing retreat-site to a new one, and distance between those successive retreat-sites) associated with the rapid acceleration of toad invasion. Over a maximum period of 70 years (∼50 generations), cane toads at the invasion front in Australia apparently have evolved such that populations include a higher proportion of individuals that make long, straight moves.