Collective cell migration plays an essential role in vertebrate development, yet the extent to which dynamically changing microenvironments influence this phenomenon remains unclear. Observations of the distribution of the extracellular matrix (ECM) component fibronectin during the migration of loosely connected neural crest cells (NCCs) lead us to hypothesize that NCC remodeling of an initially punctate ECM creates a scaffold for trailing cells, enabling them to form robust and coherent stream patterns. We evaluate this idea in a theoretical setting by developing an individual-based computational model that incorporates reciprocal interactions between NCCs and their ECM. ECM remodeling, haptotaxis, contact guidance, and cell-cell repulsion are sufficient for cells to establish streams in silico, however, additional mechanisms, such as chemotaxis, are required to consistently guide cells along the correct target corridor. Further model investigations imply that contact guidance and differential cell-cell repulsion between leader and follower cells are key contributors to robust collective cell migration by preventing stream breakage. Global sensitivity analysis and simulated gain- and loss-of-function experiments suggest that long-distance migration without jamming is most likely to occur when leading cells specialize in creating ECM fibers, and trailing cells specialize in responding to environmental cues by upregulating mechanisms such as contact guidance.