Exotic predators have been the driving force behind the extinction of many island endemic species. We examined impacts of feral cats (Felis catus) on the abundance and anti-predator behaviors of Aegean wall lizards (Podarcis erhardii) in the Cyclades (Greece), where cats were introduced thousands of years ago. We compared populations with high and low cat density on Naxos and populations on surrounding islets with no cats. Results show that cats have strong negative effects on wall lizard populations, and lizards cope with current threat from cats using plastic defenses that likely existed before the ancient introduction. Lizards facing greater risk from cats stayed closer to refugia, and were more likely to shed their tails in a standardized assay. Flight initiation distance from a surveyor or a mounted cat decoy in the lab correlated closely with risk from cats. All populations showed phenotypic plasticity in flight initiation distance suggesting that this plasticity is ancient and could have helped wall lizards survive the initial introduction of cats to the region. Lizards from islets sought shelter less often and often initially approached the cat decoy. These differences reflect a change since the introduction and could render islet lizards strongly susceptible to cat predation.