Migrating cells must interpret chemical gradients to guide themselves within tissues. A long-held principle is that gradients guide cells via reorientation of leading-edge protrusions. However, recent evidence indicates that protrusions can be dispensable for locomotion in some contexts, raising questions about how cells interpret endogenous gradients in vivo and whether other mechanisms are involved. Using laser wound assays in zebrafish to elicit acute endogenous gradients and quantitative analyses, we demonstrate a two-stage process for leukocyte chemotaxis in vivo: first a "search" phase, with stimulation of actin networks at the leading edge, cell deceleration, and turning. This is followed by a "run" phase, with fast actin flows, cell acceleration, and persistence. When actin dynamics are perturbed, cells fail to resolve the gradient, suggesting that pure spatial sensing of the gradient is insufficient for navigation. Our data suggest that cell contractility and actin flows provide memory for temporal sensing, while expansion of the leading edge serves to enhance gradient sampling.