Vulnerable native species may survive the impact of a lethally toxic invader by changes in behaviour, physiology and/or morphology. The roles of such mechanisms can be clarified by standardised testing. We recorded behavioural responses of monitor lizards (Varanus panoptes and V. varius) to legs of poisonous cane toads (Rhinella marina) and non-toxic control meals (chicken necks or chicken eggs and sardines) along 1300 and 2500 km transects, encompassing the toad's 85-year invasion trajectory across Australia as well as yet-to-be-invaded sites to the west and south of the currently colonised area. Patterns were identical in the two varanid species. Of monitors that consumed at least one prey type, 96% took control baits whereas toad legs were eaten by 60% of lizards in toad-free sites but 0% from toad-invaded sites. Our survey confirms that the ability to recognise and reject toads as prey enables monitor lizards to coexist with cane toads. As toxic invaders continue to impact ecosystems globally, it is vital to understand the mechanisms that allow some taxa to persist over long time-scales.