We study a non-Markovian and nonstationary model of animal mobility incorporating both exploration and memory in the form of preferential returns. Exact results for the probability of visiting a given number of sites are derived and a practical WKB approximation to treat the nonstationary problem is developed. A mean-field version of this model, first suggested by Song et al., [Modelling the scaling properties of human mobility, Nat. Phys. 6, 818 (2010)NPAHAX1745-247310.1038/nphys1760] was shown to well describe human movement data. We show that our generalized model adequately describes empirical movement data of Egyptian fruit bats (Rousettus aegyptiacus) when accounting for interindividual variation in the population. We also study the probability of visiting any site a given number of times and derive a mean-field equation. Our analysis yields a remarkable phase transition occurring at preferential returns which scale linearly with past visits. Following empirical evidence, we suggest that this phase transition reflects a trade-off between extensive and intensive foraging modes.