During disease and development, physical changes in extracellular matrix cause jamming, unjamming, and scattering in epithelial migration. However, whether disruptions in matrix topology alter collective cell migration speed and cell-cell coordination remains unclear. We microfabricated substrates with stumps of defined geometry, density, and orientation, which create obstructions for migrating epithelial cells. Here, we show that cells lose their speed and directionality when moving through densely spaced obstructions. Although leader cells are stiffer than follower cells on flat substrates, dense obstructions cause overall cell softening. Through a lattice-based model, we identify cellular protrusions, cell-cell adhesions, and leader-follower communication as key mechanisms for obstruction-sensitive collective cell migration. Our modeling predictions and experimental validations show that cells' obstruction sensitivity requires an optimal balance of cell-cell adhesions and protrusions. Both MDCK (more cohesive) and α-catenin-depleted MCF10A cells were less obstruction sensitive than wild-type MCF10A cells. Together, microscale softening, mesoscale disorder, and macroscale multicellular communication enable epithelial cell populations to sense topological obstructions encountered in challenging environments. Thus, obstruction-sensitivity could define "mechanotype" of cells that collectively migrate yet maintain intercellular communication.