<p>Cooperation among phenotypically distinct sub-populations within a tumor plays a key role in cancer progression. In this study, we investigated how proteolytic heterogeneity supports collective cancer invasion. In invasive MDA-MB-231 breast cancer cells which exhibit considerable variability in MMP9 expression, we show that MMP9 knockdown cells are notably smaller and softer than control cells. A computational model revealed that the invasiveness of mixed clusters containing both proteolytic and non-proteolytic cells depends on cell-cell adhesion, with non-proteolytic cell invasion requiring close proximity to proteolytic neighbors. When we assigned non-proteolytic cells the same size and stiffness as proteolytic ones, the overall invasiveness declined–highlighting that small size and deformability of non-proteolytic cells are essential for sustained collective invasion. We validated these predictions experimentally using spheroid invasion assays showing that mixed spheroids of control and MMP9 knockdown cells are the most invasive. Together, our findings demonstrate that interplay between MMP9 expression and biophysical properties enables collective invasion through enrichment of and matrix degradation by high MMP9 expressing cells at the invasive front, and squeezing of low MMP9 expressing cells through the remodeled matrix.</p>