Vertebrates exhibit extensive variation in relative brain size. It has long been assumed that this variation is the product of ecologically driven natural selection. Yet, despite more than 100 years of research, the ecological conditions that select for changes in brain size are unclear. Recent laboratory selection experiments showed that selection for larger brains is associated with increased survival in risky environments. Such results lead to the prediction that increased predation should favour increased brain size. Work on natural populations, however, foreshadows the opposite trajectory of evolution; increased predation favours increased boldness, slower learning, and may thereby select for a smaller brain. We tested the influence of predator-induced mortality on brain size evolution by quantifying brain size variation in a Trinidadian killifish, Rivulus hartii, from communities that differ in predation intensity. We observed strong genetic differences in male (but not female) brain size between fish communities; second generation laboratory-reared males from sites with predators exhibited smaller brains than Rivulus from sites in which they are the only fish present. Such trends oppose the results of recent laboratory selection experiments and are not explained by trade-offs with other components of fitness. Our results suggest that increased male brain size is favoured in less risky environments because of the fitness benefits associated with faster rates of learning and problem-solving behaviour.