Studies dating back a century (Flügge, 1934) have stressed the critical role of the wind as the primary directional cue in odor plume navigation. Here, we show that Drosophila shape their navigational decisions using a second directional cue – the direction of motion of odors – which they detect from the temporal correlations of 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 is computationally equivalent to motion detection algorithms underlying motion detection in vision. Simulations and theoretical analysis of turbulent plumes reveal that odor motion contains valuable directional information absent from the airflow; indeed, this information is used by both Drosophila and virtual agents to navigate naturalistic odor environments. The generality of our findings suggests that odor direction sensing is likely used throughout the animal kingdom, and could significantly improve olfactory robot navigation in harsh chemical environments.