Odor attraction in walking Drosophila melanogaster is commonly used to relate neural function to behavior, but the algorithms underlying attraction are unclear. Here, we develop a high-throughput assay to measure olfactory behavior in response to well-controlled sensory stimuli. We show that odor evokes two behaviors: an upwind run during odor (ON response), and a local search at odor offset (OFF response). Wind orientation requires antennal mechanoreceptors, but search is driven solely by odor. Using dynamic odor stimuli, we measure the dependence of these two behaviors on odor intensity and history. Based on these data, we develop a navigation model that recapitulates the behavior of flies in our apparatus, and generates realistic trajectories when run in a turbulent boundary layer plume. The ability to parse olfactory navigation into quantifiable elementary sensori-motor transformations provides a foundation for dissecting neural circuits that govern olfactory behavior.