The migration of cancer cells is highly regulated by the biomechanical properties of their local microenvironment. Using 3D scaffolds of simple composition, several aspects of cancer cell mechanosensing (signal transduction, EMC remodeling, traction forces) have been separately analyzed in the context of cell migration. However, a combined study of these factors in 3D scaffolds that more closely resemble the complex microenvironment of the cancer ECM is still missing. Here, we present a comprehensive, quantitative analysis of the role of cell-ECM interactions in cancer cell migration within a highly physiological environment consisting of mixed Matrigel-collagen hydrogel scaffolds of increasing complexity that mimic the tumor microenvironment at the leading edge of cancer invasion. We quantitatively show that the presence of Matrigel increases hydrogel stiffness, which promotes β1 integrin expression and metalloproteinase activity in H1299 lung cancer cells. Then, we show that ECM remodeling activity causes matrix alignment and compaction that favors higher tractions exerted by the cells. However, these traction forces do not linearly translate into increased motility due to a biphasic role of cell adhesions in cell migration: at low concentration Matrigel promotes migration-effective tractions exerted through a high number of small sized focal adhesions. However, at high Matrigel concentration, traction forces are exerted through fewer, but larger focal adhesions that favor attachment yielding lower cell motility.