Keratocytes are fast-moving cells in which adhesion dynamics are tightly coupled to the actin polymerization motor that drives migration, resulting in highly coordinated cell movement. We have found that modifying the adhesive properties of the underlying substrate has a dramatic effect on keratocyte morphology. Cells crawling at intermediate adhesion strengths resembled stereotypical keratocytes, characterized by a broad, fan-shaped lamellipodium, clearly defined leading and trailing edges, and persistent rates of protrusion and retraction. Cells at low adhesion strength were small and round with highly variable protrusion and retraction rates, and cells at high adhesion strength were large and asymmetrical and, strikingly, exhibited traveling waves of protrusion. To elucidate the mechanisms by which adhesion strength determines cell behavior, we examined the organization of adhesions, myosin II, and the actin network in keratocytes migrating on substrates with different adhesion strengths. On the whole, our results are consistent with a quantitative physical model in which keratocyte shape and migratory behavior emerge from the self-organization of actin, adhesions, and myosin, and quantitative changes in either adhesion strength or myosin contraction can switch keratocytes among qualitatively distinct migration regimes.