Productive cell migration requires the spatiotemporal coordination of cell adhesion, membrane protrusion, and actomyosin-mediated contraction. Integrins, engaged by the extracellular matrix (ECM), nucleate the formation of adhesive contacts at the cell's leading edge(s), and maturation of nascent adhesions to form stable focal adhesions constitutes a functional switch between protrusive and contractile activities. To shed additional light on the coupling between integrin-mediated adhesion and membrane protrusion, we have formulated a quantitative model of leading edge dynamics combining mechanistic and phenomenological elements and studied its features through classical bifurcation analysis and stochastic simulation. The model describes in mathematical terms the feedback loops driving, on the one hand, Rac-mediated membrane protrusion and rapid turnover of nascent adhesions, and on the other, myosin-dependent maturation of adhesions that inhibit protrusion at high ECM density. Our results show that the qualitative behavior of the model is most sensitive to parameters characterizing the influence of stable adhesions and myosin. The major predictions of the model, which we subsequently confirmed, are that persistent leading edge protrusion is optimal at an intermediate ECM density, whereas depletion of myosin IIA relieves the repression of protrusion at higher ECM density.