Adult fruit flies follow attractive odors associated with food and oviposition sites through widely varied visual landscapes. To examine the interaction between olfactory and visual cues during search behavior, we recorded three-dimensional flight trajectories as individuals explored controlled sensory landscapes. When presented with the source of an attractive odor invisibly embedded in the floor of a 1 m arena, flies spend most of their time hovering back and forth over the source when flying within a randomly textured visual background but fail to localize the source when searching within a uniform white surround. To test whether flies are associating unique features of the visual background with the strength of odor cues, we flew them within arenas containing evenly spaced vertical stripes. Flies readily localized the odor when flying within visual landscapes lacking azimuthal landmarks provided that vertical edges were present. Flies failed to localize odor when flying within a background pattern consisting of horizontal stripes. These results suggest that, whereas flies do not require spatially unique visual patterns to localize an odor source, they do require visual feedback generated by vertical edges. Quantitative shifts in several components of flight behavior accompanied successful odor localization. Flies decrease flight altitude, turn more often and approach visually textured walls of the arena near an odor source. A simple model based on the statistics of flight behavior supports the hypothesis that a subtle influence on these behaviors is sufficient to lead a fly to its food.