A general theory of animal movement can be formulated within a mathematical framework drawn from statistical physics. Although animals are much more complex than particles, animal movements generate statistical regularities that are propagated through identifiable scales; these regularities are much more fundamental than species-specific details. Often, the observed statistical regularities are considered as emergent properties that are useful for modeling purposes, but with no real biological meaning. However, in the context of animal foraging, it has been shown that some statistical properties (i.e., super-diffusion, scale-invariance, intermittence) can enhance encounter success by solving general search and/or ecological trade-offs. This finding calls into question previous interpretations of the role of stochastic models (e.g., random walk models) in animal movement, and sets the scene for understanding how evolution has shaped random search strategies. Studying the statistical properties of movement in the light of evolution is a challenge that can help us to predict relevant statistical outputs across ecological scales and species.