How insects navigate complex odor plumes, where the location and timing of odor packets are uncertain, remains unclear. Here we imaged complex odor plumes simultaneously with freely-walking flies, quantifying how behavior is shaped by encounters with individual odor packets. We found that navigation was stochastic and did not rely on the continuous modulation of speed or orientation. Instead, flies turned stochastically with stereotyped saccades, whose direction was biased upwind by the timing of prior odor encounters, while the magnitude and rate of saccades remained constant. Further, flies used the timing of odor encounters to modulate the transition rates between walks and stops. In more regular environments, flies continuously modulate speed and orientation, even though encounters can still occur randomly due to animal motion. We find that in less predictable environments, where encounters are random in both space and time, walking flies navigate with random walks biased by encounter timing., eLife digest When walking along a city street, you might encounter a range of scents and odors, from the smells of coffee and food to those of exhaust fumes and garbage. The odors are swept to your nose by air currents that move scents in two different ways. They carry them downwind in a process called advection, but they also mix them chaotically with clean air in a process called turbulence. What results is an odor plume: a complex ever-changing structure resembling the smoke rising from a chimney. Within a plume, areas of highly concentrated odor particles break up into smaller parcels as they travel further from the odor source. This means that the concentration of the odor does not vary along a smooth gradient. Instead, the odor arrives in brief and unpredictable bursts. Despite this complexity, insects are able to use odor plumes with remarkable ease to navigate towards food sources. But how do they do this? Answering this question has proved challenging because odor plumes are usually invisible. Over the years, scientists have come up with a number of creative solutions to this problem, including releasing soap bubbles together with odors, or using wind tunnels to generate simpler, straight plumes in known locations. These approaches have shown that when insects encounter an odor, they surge upwind towards its source. When they lose track of the odor, they cast themselves crosswind in an effort to regain contact. But this does not explain how insects are able to navigate irregular odor plumes, in which both the timing and location of the odor bursts are unpredictable. Demir, Kadakia et al. have now bridged this gap by showing how fruit flies are attracted to smoke, an odorant that is also visible. By injecting irregular smoke plumes into a custom-built wind tunnel, and then imaging flies as they walked through it, Demir, Kadakia et al. showed that flies make random halts when navigating the plume. Each time they stop, they use the timing of the odor bursts reaching them to decide when to start moving again. Rather than turning every time they detect an odor, flies initiate turns at random times. When several odor bursts arrive in a short time, the flies tend to orient these turns upwind rather than downwind. Flies therefore rely on a different strategy to navigate irregular odor plumes than the ‘surge and cast’ method they use for regular odor streams. Successful navigation through complex irregular plumes involves a degree of random behavior. This helps the flies gather information about an unpredictable environment as they search for the source of the odor. These findings may help to understand how other insects use odor to navigate in the real world, for example, how mosquitoes track down human hosts.