Cells crawling through tissues migrate inside a complex fibrous environment called the extracellular matrix (ECM), which provides signals regulating motility. Here we investigate one such well-known pathway, involving mutually antagonistic signalling molecules (small GTPases Rac and Rho) that control the protrusion and contraction of the cell edges (lamellipodia). Invasive melanoma cells were observed migrating on surfaces with topography (array of posts), coated with adhesive molecules (fibronectin, FN) by Park et al., 2016. Several distinct qualitative behaviors they observed included persistent polarity, oscillation between the cell front and back, and random dynamics. To gain insight into the link between intracellular and ECM signaling, we compared experimental observations to a sequence of mathematical models encoding distinct hypotheses. The successful model required several critical factors. (1) Competition of lamellipodia for limited pools of GTPases. (2) Protrusion / contraction of lamellipodia influence ECM signaling. (3) ECM-mediated activation of Rho. A model combining these elements explains all three cellular behaviors and correctly predicts the results of experimental perturbations. This study yields new insight into how the dynamic interactions between intracellular signaling and the cells environment influence cell behavior.