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. Cell migration is important for many biological processes: white blood cells chase down and kill bacteria to guard against infection, epithelial cells crawl across open wounds to promote healing, and embryonic cells move collectively to form organs and tissues during embryogenesis. In all of these cases, migration depends on the spatial and temporal organization of multiple forces, including actin-driven protrusion of the cell membrane, membrane tension, cell-substrate adhesion, and myosin-mediated contraction of the actin network. In this work, we have used a simple cell type, the fish epithelial keratocyte, as a model system to investigate the manner in which these forces are integrated to give rise to large-scale emergent properties such as cell shape and movement. Keratocytes are normally fan-shaped and fast-moving, but we have found that keratocytes migrate more slowly and assume round or asymmetric shapes when cell-substrate adhesion strength is too high or too low. By correlating measurements of adhesion-dependent changes in cell shape and speed with measurements of adhesion and myosin localization patterns and actin network organization, we have developed a mechanical model in which keratocyte shape and movement emerge from adhesion and myosin-dependent regulation of the dynamic actin cytoskeleton.