Cell migration toward areas of higher extracellular matrix (ECM) rigidity via a process called "durotaxis" is thought to contribute to development, immune response, and cancer metastasis. To understand how cells sample ECM rigidity to guide durotaxis, we characterized cell-generated forces on the nanoscale within single mature integrin-based focal adhesions (FAs). We found that individual FAs act autonomously, exhibiting either stable or dynamically fluctuating ("tugging") traction. We show that a FAK/phosphopaxillin/vinculin pathway is essential for high FA traction and to enable tugging FA traction over a broad range of ECM rigidities. We show that tugging FA traction is dispensable for FA maturation, chemotaxis, and haptotaxis but is critical to direct cell migration toward rigid ECM. We conclude that individual FAs dynamically sample rigidity by applying fluctuating pulling forces to the ECM to act as sensors to guide durotaxis, and that FAK/phosphopaxillin/vinculin signaling defines the rigidity range over which this dynamic sensing process operates.