Natural selection is often invoked to explain differences in brain size among vertebrates. However, the particular agents of selection that shape brain size variation remain obscure. Recent studies suggest that predators may select for larger brains because increased cognitive and sensory abilities allow prey to better elude predators. Yet, there is little direct evidence that exposure to predators causes the evolution of larger brains in prey species. We experimentally tested this prediction by exposing families of 1000-2000 F2 hybrid benthic-limnetic threespine stickleback to predators under naturalistic conditions, along with matched controls. After two generations of selection, we found that fish from the predator addition treatment had significantly smaller brains (specifically smaller telencephalons and optic lobes) than fish from the control treatment. After an additional generation of selection, we reared experimental fish in a common environment and found that this difference in brain size was maintained in the offspring of fish from the predator addition treatment. Our results provide direct experimental evidence that (a) predators can indeed drive the evolution of brain size – but not in the fashion commonly expected and (b) that the tools of experimental evolution can be used to the study the evolution of the vertebrate brain.