Cells move differently on substrates with different rigidities: the persistence time of their motion is higher on stiffer substrates. We show that this behavior—in and of itself—results in a net flux of cells directed up a soft-to-stiff gradient. Using simple random walk models with varying persistence and stochastic simulations, we characterize the propensity to move in terms of the durotactic index also measured in experiments. A one-dimensional model captures the essential features and highlights the competition between diffusive spreading and linear, wavelike propagation. Persistence-driven durokinesis is generic and may be of use in the design of instructive environments for cells and other motile, mechanosensitive objects.