Living cells actively migrate in their environment to perform key biological functions-from unicellular organisms looking for food to single cells such as fibroblasts, leukocytes or cancer cells that can shape, patrol or invade tissues. Cell migration results from complex intracellular processes that enable cell self-propulsion, and has been shown to also integrate various chemical or physical extracellular signals. While it is established that cells can modify their environment by depositing biochemical signals or mechanically remodelling the extracellular matrix, the impact of such self-induced environmental perturbations on cell trajectories at various scales remains unexplored. Here, we show that cells can retrieve their path: by confining motile cells on 1D and 2D micropatterned surfaces, we demonstrate that they leave long-lived physicochemical footprints along their way, which determine their future path. On this basis, we argue that cell trajectories belong to the general class of self-interacting random walks, and show that self-interactions can rule large scale exploration by inducing long-lived ageing, subdiffusion and anomalous first-passage statistics. Altogether, our joint experimental and theoretical approach points to a generic coupling between motile cells and their environment, which endows cells with a spatial memory of their path and can dramatically change their space exploration.