Many predator species attempt to locate prey by following seemingly random paths. Although the underlying physical mechanism of the search remains largely unknown, such search paths are usually modeled by some type of random walk. Here, we introduce the stochastic pursuit-evasion equations that consider the bidirectional interaction between predators and prey. This assumption results in a modulated persistent random walk that is characterized by three interesting properties: power-law or tempered power-law distributed running times, superdiffusive or transient superdiffusive dynamics, and strong directional persistence. Furthermore, the proposed model exhibits a transition from Brownian to Lévy-like motion with intensifying predator–prey interaction. Interestingly, persistent random walks with pure-power law distributed running times emerge at the limit of highest predator–prey interaction. We hypothesize that the system ultimately self-organizes into a critical interaction to avoid extinction.