Odor plumes in the wild are spatially complex and rapidly fluctuating structures carried by turbulent airflows. To successfully navigate plumes in search of food and mates, insects must extract and integrate multiple features of the odor signal, including odor identity, intensity, and timing. Effective navigation requires balancing these multiple streams of olfactory information and integrating them with other sensory inputs, including visual and mechanosensory cues. Studies dating back a century have indicated that, of these many sensory inputs, the wind provides the main directional cue in turbulent plumes, leading to the longstanding model of insect odor navigation as odor-elicited upwind motion. Here, we show that Drosophila shape their navigational decisions using an additional directional cue – the direction of motion of odors – which they detect using temporal correlations in the odor signal between their two antennae. Using a high-resolution virtual reality paradigm to deliver spatiotemporally complex fictive odors to freely-walking flies, we demonstrate that such odor direction sensing employs algorithms analogous to those in visual direction sensing. Combining simulations, theory, and experiments, we show that odor motion contains valuable directional information absent from the airflow alone and that both Drosophila and virtual agents are aided by that information in navigating naturalistic plumes. The generality of our findings suggests that odor direction sensing may exist throughout the animal kingdom and could improve olfactory robot navigation in uncertain environments.