Cell migration on 2D surfaces is governed by a balance between counteracting tractile and adhesion forces. Although biochemical factors such as adhesion receptor and ligand concentration and binding, signaling through cell adhesion complexes, and cytoskeletal structure assembly/disassembly have been studied in detail in a 2D context, the critical biochemical and biophysical parameters that affect cell migration in 3D matrices have not been quantitatively investigated. We demonstrate that, in addition to adhesion and tractile forces, matrix stiffness is a key factor that influences cell movement in 3D. Cell migration assays in which Matrigel density, fibronectin concentration, and beta1 integrin binding are systematically varied show that at a specific Matrigel density the migration speed of DU-145 human prostate carcinoma cells is a balance between tractile and adhesion forces. However, when biochemical parameters such as matrix ligand and cell integrin receptor levels are held constant, maximal cell movement shifts to matrices exhibiting lesser stiffness. This behavior contradicts current 2D models but is predicted by a recent force-based computational model of cell movement in a 3D matrix. As expected, this 3D motility through an extracellular environment of pore size much smaller than cellular dimensions does depend on proteolytic activity as broad-spectrum matrix metalloproteinase (MMP) inhibitors limit the migration of DU-145 cells and also HT-1080 fibrosarcoma cells. Our experimental findings here represent, to our knowledge, discovery of a previously undescribed set of balances of cell and matrix properties that govern the ability of tumor cells to migration in 3D environments.