Despite the importance of matrix rigidity on cell functions, many aspects of the mechanosensing process in highly migratory cells remain elusive. Here, we studied the migration of highly motile keratocytes on culture substrates with similar biochemical properties and rigidities spanning the range between soft tissues (~kPa) and stiff culture substrates (~GPa). We show that morphology, polarization and persistence of motile keratocytes are regulated by the matrix stiffness over seven orders of magnitude, without changing the cell spreading area. Increasing the matrix rigidity leads to more F-actin in the lamellipodia and to the formation of mature contractile actomyosin fibers that control the cell rear retraction. Keratocytes remain rounded and form nascent adhesions on compliant substrates, whereas large and uniformly distributed focal adhesions are formed on fan-shaped keratocytes migrating on rigid surfaces. By combining poly-L-lysine, fibronectin and vitronectin coatings with selective blocking of αvβ3 or α5β1 integrins, we show that αVβ3 integrins permit the spreading of keratocytes but are not sufficient for polarization and rigidity sensing that require the engagement of α5β1 integrins. Our study demonstrates a matrix rigidity-dependent regulation of the directional persistence in motile keratocytes and refines the role of αvβ3 and α5β1 integrins in the molecular clutch model.