The coevolution of predators and prey has been the subject of much empirical and theoretical research that produced intriguing insights into the interplay of ecology and evolution. To allow for mathematical analysis, models of predator–prey coevolution are often coarse-grained, focussing on population-level processes and largely neglecting individual-level behaviour. As selection is acting on individual-level properties, we here present a more mechanistic approach: an individual-based simulation model for the coevolution of predators and prey on a fine-grained resource landscape, where features relevant for ecology (like changes in local densities) and evolution (like differences in survival and reproduction) emerge naturally from interactions between individuals. Our focus is on predator–prey movement behaviour, and we present a new method for implementing evolving movement strategies in an efficient and intuitively appealing manner. Throughout their lifetime, predators and prey make repeated movement decisions on the basis of their movement strategies. Over the generations, the movement strategies evolve, as individuals that successfully survive and reproduce leave their strategy to more descendants. We show that the movement strategies in our model evolve rapidly, thereby inducing characteristic spatial patterns like spiral waves and static spots. Transitions between these patterns occur frequently, induced by antagonistic coevolution rather than by external events. Regularly, evolution leads to the emergence and stable coexistence of qualitatively different movement strategies within the same population. Although the strategy space of our model is continuous, we often observe the evolution of discrete movement types. We argue that rapid evolution, coexistent movement types, and phase shifts between different ecological regimes are not a peculiarity of our model but a result of more realistic assumptions on eco-evolutionary feedbacks and the number of evolutionary degrees of freedom.