Cell polarization and directional cell migration can display random, persistent and oscillatory dynamic patterns. However, it is not clear if these polarity patterns can be explained by the same underlying regulatory mechanism. Here, we show that random, persistent and oscillatory migration accompanied by polarization can simultaneously occur in populations of melanoma cells derived from tumors with different degrees of aggressiveness. We demonstrate that all these patterns and the probabilities of their occurrence are quantitatively accounted for by a simple mechanism involving a spatially distributed, mechano-chemical feedback coupling the dynamically changing extracellular matrix (ECM)-cell contacts to the activation of signaling downstream of the Rho-family small GTPases. This mechanism is supported by a predictive mathematical model and extensive experimental validation, and can explain previously reported results for diverse cell types. In melanoma, this mechanism also accounts for the effects of genetic and environmental perturbations, including mutations linked to invasive cell spread. The resulting mechanistic understanding of cell polarity quantitatively captures the relationship between population variability and phenotypic plasticity, with the potential to account for a wide variety of cell migration states in diverse pathological and physiological conditions.