Actin polymerization-driven protrusion of the lamellipodia is a requisite initial step during actin-based cell migration, and is closely associated with attachment to the substrate. Although tremendous progress has been made in recent years toward elucidating the molecular details of focal adhesions, our understanding of the basic coordination of protrusion and adhesion, and how the two fundamental processes relate to actomyosin contractility is still inadequate. Therefore, to highlight the effect of cell-substrate interactions on the protrusive dynamics of the lamellipodia and to correlate protrusion with actomyosin activities, this study investigated the migration of fish epidermal keratocytes on fibronectin micropatterns intercalated with adhesion-suppressed gaps of varying widths. We show that insufficient adhesion associated with the gaps could limit lamellipodial protrusion such that the percentage of migrating cells decreases with an increase in gap width, and protrusion across the gaps is accompanied by ruffling. Moreover, our results suggest that up-regulating actomyosin contractility enhances the mechanical integrity of the actin cytoskeleton, leading to an increase in the width of the lamellipodia, and consequently, an increase in the percentage of cells migrating across the gaps. Thus, we demonstrate that the protrusion dynamics at the leading edge of migrating cells are functionally involved in the global mechanical regulation of actin cytoskeletal components that enable cell migration.