To move forward, migrating cells must generate traction forces through surface receptors bound to extracellular matrix molecules coupled to a rigid structure. We investigated whether cells sample and respond to the rigidity of the anchoring matrix. Movement of beads coated with fibronectin or an anti-integrin antibody was restrained with an optical trap on fibroblasts to mimic extracellular attachment sites of different resistance. Cells precisely sense the restraining force on fibronectin beads and respond by a localized, proportional strengthening of the cytoskeleton linkages, allowing stronger force to be exerted on the integrins. This strengthening was absent or transient with antibody beads, but restored with soluble fibronectin. Hence, ligand binding site occupancy was required. Finally, phenylarsine oxide inhibited strengthening of cytoskeletal linkages, indicating a role for dephosphorylation. Thus, the strength of integrin-cytoskeleton linkages is dependent on matrix rigidity and on its biochemical composition. Matrix rigidity may, therefore, serve as a guidance cue in a process of mechanotaxis.