Many diffusion processes in nature and society were found to be anomalous, in the sense of being fundamentally different from conventional Brownian motion. An important example is the migration of biological cells, which exhibits non-trivial temporal decay of velocity autocorrelation functions. This means that the corresponding dynamics is characterized by memory effects that slowly decay in time. Motivated by this we construct non-Markovian lattice-gas cellular automata models for moving agents with memory. For this purpose the reorientation probabilities are derived from velocity autocorrelation functions that are given a priori; in that respect our approach is "data-driven". Particular examples we consider are velocity correlations that decay exponentially or as power laws, where the latter functions generate anomalous diffusion. The computational efficiency of cellular automata combined with our analytical results paves the way to explore the relevance of memory and anomalous diffusion for the dynamics of interacting cell populations, like confluent cell monolayers and cell clustering. © 2017 The Author(s).