On rigid surfaces, the cytoskeleton of migrating cells is polarized, but tissue matrix is normally soft. We show that nonmuscle MIIB (myosin-IIB) is unpolarized in cells on soft matrix in 2D and also within soft 3D collagen, with rearward polarization of MIIB emerging only as cells migrate from soft to stiff matrix. Durotaxis is the tendency of cells to crawl from soft to stiff matrix, and durotaxis of primary mesenchymal stem cells (MSCs) proved more sensitive to MIIB than to the more abundant and persistently unpolarized nonmuscle MIIA (myosin-IIA). However, MIIA has a key upstream role: in cells on soft matrix, MIIA appeared diffuse and mobile, whereas on stiff matrix, MIIA was strongly assembled in oriented stress fibers that MIIB then polarized. The difference was caused in part by elevated phospho-S1943-MIIA in MSCs on soft matrix, with site-specific mutants revealing the importance of phosphomoderated assembly of MIIA. Polarization is thus shown to be a highly regulated compass for mechanosensitive migration.