abstract: In regular, discrete-time quantum walks, the Hilbert space is bipartite, comprising position and coin degrees of freedom. We introduce a formalism for quantum walks with memory, where the coin parameter is replaced with a register of coins that record the coin history going back a fixed number of steps. The walker evolves as a function of the coin register, which is updated via a memory function. We consider different memory functions and explore their effect on the dynamics of the walk. In one dimension, walkers with memory consistently exhibit ballistic speedup compared to classical walks. However, the choice of memory function drastically affects the dynamics and rate of spread. Measurement of the coin registers dramatically changes the dynamics of the walk. Next we consider a two-dimensional walk, and find that memory destroys the entanglement between the spatial dimensions, even when spatially entangling coins are employed. We present a physical model for how such a quantum walk might be implemented with linear optics, paving the way for experimental construction of such a walk. We discuss the computational power of multi-walker quantum walks with memory, and suggest that they might implement a classically hard algorithm, making them of experimental interest.