Migration of cells is integral in various physiological processes in all facets of life. These range from embryonic development, morphogenesis, and wound healing, to disease pathology such as cancer metastasis. While cell migratory behavior has been traditionally studied using simple assays on culture dishes, in recent years it has been increasingly realized that the physical, mechanical, and chemical aspects of the matrix are key determinants of the migration mechanism. In this paper, we will describe the mechanobiological changes that accompany the dynamic cell–matrix interactions during cell migration. Furthermore, we will review what is to date known about how these changes feed back to the dynamics and biomechanical properties of the cell and the matrix. Elucidating the role of these intimate cell–matrix interactions will provide not only a better multi-scale understanding of cell motility in its physiological context, but also a more holistic perspective for designing approaches to regulate cell behavior.