Phenotypic heterogeneity is increasingly acknowledged to confer several advantages to cancer progression and drug resistance. Here, we probe the collective importance of heterogeneity in cell size and deformability in breast cancer invasion. A computational model of invasion of a heterogeneous cell aggregate predicts that combined heterogeneity in cell size and deformability enhances invasiveness of the whole population, with maximum invasiveness at intermediate cell-cell adhesion. We then show that small cells of varying deformability, a subpopulation predicted to be enriched at the invasive front, exhibit considerable overlap with the biophysical properties of cancer stem cells (CSCs). In MDA-MB-231 cells, these include CD44hi CD24− mesenchymal CSCs, which are small and soft, and CD44hi CD24+ hybrid CSCs, which exhibit a wide range of size and deformability. We validate our predictions by tracking the pattern of cell invasion from spheroids implanted in three-dimensional collagen gels, wherein we show temporal enrichment of CD44hi cells at the invasive front. Collectively, our results illustrate the advantages imparted by biophysical heterogeneity in enhancing cancer invasiveness.