The interaction of the actin cytoskeleton with cell–substrate adhesions is necessary for cell migration. While the trajectories of motile cells have a stochastic character, investigations of cell motility mechanisms rarely elaborate on the origins of the observed randomness. Here, guided by a few fundamental attributes of cell motility, I construct a minimal stochastic cell migration model from ground-up. The resulting model couples a deterministic actomyosin contractility mechanism with stochastic cell–substrate adhesion kinetics, and yields a well-defined piecewise deterministic process. Numerical simulations reproduce several experimentally observed results, including anomalous diffusion, tactic migration and contact guidance. This work provides a basis for the development of cell–cell collision and population migration models.