Plastic changes in behavior can allow animals to adapt to changes in their environment, but the adaptive role of rapid behavioral adjustments for surviving anthropogenically-induced environmental change is less well understood, especially with regard to behavioral plasticity facilitating the evolution of other traits. Here we examine the ability of lizards to rapidly acquire adaptive antipredator behavior following a single predator exposure. Fence lizards typically rely on crypsis to avoid predator detection, but this is maladaptive in the face of invasive venomous fire ants that can successfully locate and attack immobile lizards. Fire ant-naïve juvenile lizards shifted their behavior to flee from fire ant attack after a single encounter with these predatory ants. Our results provide evidence of rapid phenotypic accommodation to an environmental threat that likely played a role in population persistence after fire ant invasion and subsequent evolution of multiple traits.