Cells exhibit a biphasic migration-velocity response to increasing adhesion strength, with fast migration occurring at intermediate extracellular matrix (ECM) concentration and slow migration occurring at low and high ECM concentration. A simple mechanical model has been proposed to explain this observation, in which too little adhesion does not provide sufficient traction whereas too much adhesion renders cells immobile. Here we characterize a phenotype for rapid cell migration, which in contrast to the previous model reveals a complex interdependence of subcellular systems that mediates optimal cell migration in response to increasing adhesion strength. The organization and activity of actin, myosin II, and focal adhesions (FAs) are spatially and temporally highly variable and do not exhibit a simple correlation with optimal motility rates. Furthermore, we can recapitulate rapid migration at a nonoptimal ECM concentration by manipulating myosin II activity. Thus, the interplay between actomyosin and FA dynamics results in a specific balance between adhesion and contraction, which induces maximal migration velocity.