Natural disturbance regimes--cycles of fire, flood, drought or other events--range from highly predictable (disturbances occur regularly in time or in concert with a proximate cue) to highly unpredictable. While theory predicts how populations should evolve under different degrees of disturbance predictability, there is little empirical evidence of how this occurs in nature. Here, we demonstrate local adaptation in populations of an aquatic insect occupying sites along a natural gradient of disturbance predictability, where predictability was defined as the ability of a proximate cue (rainfall) to signal a disturbance (flash flood). In controlled behavioural experiments, populations from predictable environments responded to rainfall events by quickly exiting the water and moving sufficiently far from the stream to escape flash floods. By contrast, populations from less predictable environments had longer response times and lower response rates, reflecting the uncertainty inherent to these environments. Analysis with signal detection theory showed that for 13 out of 15 populations, observed response times were an optimal compromise between the competing risks of abandoning versus remaining in the stream, mediated by the rainfall-flood correlation of the local environment. Our study provides the first demonstration that populations can evolve in response to differences in disturbance predictability, and provides evidence that populations can adapt to among-stream differences in flow regime.