Motile eukaryotic cells migrate with directional persistence by alternating left and right turns, even in the absence of external cues. For example, Dictyostelium discoideum cells crawl by extending distinct pseudopods in an alternating right-left pattern. The mechanisms underlying this zig-zag behavior, however, remain unknown. Here we propose a new Excitable Cortex and Memory (EC&M) model for understanding the alternating, zig-zag extension of pseudopods. Incorporating elements of previous models, we consider the cell cortex as an excitable system and include global inhibition of new pseudopods while a pseudopod is active. With the novel hypothesis that pseudopod activity makes the local cortex temporarily more excitable--thus creating a memory of previous pseudopod locations--the model reproduces experimentally observed zig-zag behavior. Furthermore, the EC&M model makes four new predictions concerning pseudopod dynamics. To test these predictions we develop an algorithm that detects pseudopods via hierarchical clustering of individual membrane extensions. Data from cell-tracking experiments agrees with all four predictions of the model, revealing that pseudopod placement is a non-Markovian process affected by the dynamics of previous pseudopods. The model is also compatible with known limits of chemotactic sensitivity. In addition to providing a predictive approach to studying eukaryotic cell motion, the EC&M model provides a general framework for future models, and suggests directions for new research regarding the molecular mechanisms underlying directional persistence.