Cell migration is hypothesized to involve a cycle of behaviours beginning with leading edge extension. However, recent evidence suggests that the leading edge may be dispensable for migration, raising the question of what actually controls cell directionality. Here, we exploit the embryonic migration of Drosophila macrophages to bridge the different temporal scales of the behaviours controlling motility. This approach reveals that edge fluctuations during random motility are not persistent and are weakly correlated with motion. In contrast, flow of the actin network behind the leading edge is highly persistent. Quantification of actin flow structure during migration reveals a stable organization and asymmetry in the cell-wide flowfield that strongly correlates with cell directionality. This organization is regulated by a gradient of actin network compression and destruction, which is controlled by myosin contraction and cofilin-mediated disassembly. It is this stable actin-flow polarity, which integrates rapid fluctuations of the leading edge, that controls inherent cellular persistence.