The ecological processes underlying locust swarm formation are poorly understood. Locust species exhibit phenotypic plasticity in numerous morphological, physiological and behavioural traits as their population density increases. These density-dependent changes are commonly assumed to be adaptations for migration under heterogeneous environmental conditions. Here we demonstrate that density-dependent nymphal colour change in the desert locust Schistocerca gregaria (Orthoptera: Acrididae) results in warning coloration (aposematism) when the population density increases and locusts consume native, toxic host plants. Fringe-toed lizards (Acanthodactylus dumerili (Lacertidae)) developed aversions to high-density-reared (gregarious-phase) locusts fed Hyoscyamus muticus (Solanaceae). Lizards associated both olfactory and visual cues with locust unpalatability, but only gregarious-phase coloration was an effective visual warning signal. The lizards did not associate low rearing density coloration (solitarious phase) with locust toxicity. Predator learning of density-dependent warning coloration results in a marked decrease in predation on locusts and may directly contribute to outbreaks of this notorious pest.