Flying insects routinely forage in complex and cluttered sensory environments. Their search for a food or a pheromone source typically begins with a whiff of odor, which triggers a flight response, eventually bringing the insect near the odor source. However, pinpointing the precise location of an odor source requires use of both visual and olfactory modalities, aided by odor plumes. Here, we investigated odor-tracking behavior in fruit flies (Drosophila melanogaster) presented with low- or high-contrast visual landmarks, either paired with or separate from an attractive odor cue. These experiments were conducted either in a gentle air stream which generated laminar odor plumes or in still air in which odor dissipates uniformly in all directions. Trajectories of flies revealed several novel features of their odor-tracking behavior in addition to those previously documented. First, in both moving and still air, odor-seeking flies rely on the co-occurrence of visual landmarks with olfactory cues to guide them to odorant objects. Second, flies abruptly decelerate upon encountering an odor plume, thereafter steering towards the nearest visual objects that had no inherent salience in the absence of odor. Thus, interception of an attractive odor increases their salience to nearby high-contrast visual landmarks. Third, flies adopt distinct odor-tracking strategies during flight in moving versus still air. Whereas they weave in and out of plumes towards an odor source in airflow, their approach is more incremental in still air. Both strategies are robust and flexible, and enable flies to reliably find odor sources under diverse visual and airflow environments.