Nearly all motile organisms must search for food, often requiring multiple phases of exploration across heterogeneous environments. The fruit fly, Drosophila, has emerged as an effective model system for studying this behavior; however, little is known about the extent to which experiences at one point in their search might influence decisions in another. To investigate whether prior experiences impact flies’ search behavior after landing, I tracked individually labelled fruit flies as they explored three odor-emitting but food-barren objects. I found two features of their behavior that are correlated with the distance they travel on foot. First, flies walked larger distances when they approached the odor source, which they were almost twice as likely to do when landing on the patch farthest downwind. Computational fluid dynamics simulations suggest this patch may have had a stronger baseline odor, but only ∼15% higher than the other two patches. This small increase, together with flies’ high olfactory sensitivity, suggests that their flight trajectory used to approach the patches plays a role. Second, flies also walked larger distances when the time elapsed since their last visit was longer. However, the correlation is subtle and subject to a large degree of variability. Using agent-based models, I show that this small correlation can increase search efficiency by 25–50% across many scenarios. Furthermore, my models provide mechanistic hypotheses explaining the variability through either a noisy or stochastic decision-making process. Surprisingly, these stochastic decision-making algorithms enhance search efficiency in challenging but realistic search scenarios compared with deterministic strategies.