Animal cell migration is a complex process characterized by the coupling of adhesion, cytoskeletal, and signaling dynamics. Here we model local protrusion of the cell edge as a function of the load-bearing properties of integrin-based adhesions, actin polymerization fostered by adhesion-mediated signaling, and mechanosensitive activation of RhoA that promotes myosin II-generated stress on the lamellipodial F-actin network. Analysis of stochastic model simulations illustrates how these pleiotropic functions of nascent adhesions may be integrated to govern temporal persistence and frequency of protrusions. The simulations give mechanistic insight into the documented effects of extracellular matrix density and myosin abundance, and they show characteristic, nonnormal distributions of protrusion duration times that are similar to those extracted from live-cell imaging experiments. Analysis of the model further predicts relationships between measurable quantities that reflect the partitioning of stress between tension on F-actin-bound adhesions, which act as a molecular clutch, and dissipation by retrograde F-actin flow.