Amoeboid cells constantly change shape and extend protrusions. The direction of movement is not random, but is correlated with the direction of movement in the preceding minutes. The basis of this correlation is an underlying memory of direction. The presence of memory in movement is known for many decades, but its molecular mechanism is still largely unknown. This study reports in detail on the information content of directional memory, the kinetics of learning and forgetting this information, and the molecular basis for memory using Dictyostelium mutants. Two types of memory were characterized. A short-term memory stores for ~20 seconds the position of the last pseudopod using a local modification of the branched F-actin inducer SCAR/WAVE, which enhances one new pseudopod to be formed at the position of the previous pseudopod. A long term memory stores for ~2 minutes the activity of the last ~10 pseudopods using a cGMP-binding protein that induces myosin filaments in the rear of the cell; this inhibits pseudopods in the rear and thereby enhances pseudopods in the global front. Similar types of memory were identified in human neutrophils and mesenchymal stem cells, the protist Dictyostelium and the fungus B.d. chytrid. The synergy of short- and long-term memory explains their role in persistent movement for enhanced cell dispersal, food seeking and chemotaxis.