Cell migration in the absence of external cues is well described by a correlated random walk. Most single cells move by extending protrusions called pseudopodia. To deduce how cells walk, we have analyzed the formation of pseudopodia by Dictyostelium cells. We have observed that the formation of pseudopodia is highly ordered with two types of pseudopodia: First, de novo formation of pseudopodia at random positions on the cell body, and therefore in random directions. Second, pseudopod splitting near the tip of the current pseudopod in alternating right/left directions, leading to a persistent zig-zag trajectory. Here we analyzed the probability frequency distributions of the angles between pseudopodia and used this information to design a stochastic model for cell movement. Monte Carlo simulations show that the critical elements are the ratio of persistent splitting pseudopodia relative to random de novo pseudopodia, the Left/Right alternation, the angle between pseudopodia and the variance of this angle. Experiments confirm predictions of the model, showing reduced persistence in mutants that are defective in pseudopod splitting and in mutants with an irregular cell surface.