Stress fibers (SFs) are actomyosin bundles commonly found in individually migrating cells in culture. However, whether and how cells use SFs to migrate in vivo or collectively is largely unknown. Studying the collective migration of the follicular epithelial cells in Drosophila, we found that the SFs in these cells show a novel treadmilling behavior that allows them to persist as the cells migrate over multiple cell lengths. Treadmilling SFs grow at their fronts by adding new integrin-based adhesions and actomyosin segments over time. This causes the SFs to have many internal adhesions along their lengths, instead of adhesions only at the ends. The front-forming adhesions remain stationary relative to the substrate and typically disassemble as the cell rear approaches. By contrast, a different type of adhesion forms at the SF’s terminus that slides with the cell’s trailing edge as the actomyosin ahead of it shortens. We further show that SF treadmilling depends on cell movement and identify a developmental switch in the formins that mediate SF assembly, with Dishevelled-associated activator of morphogenesis acting during migratory stages and Diaphanous acting during postmigratory stages. We propose that treadmilling SFs keep each cell on a linear trajectory, thereby promoting the collective motility required for epithelial migration.