The availability of food resources changes over time and space, and foraging animals are constantly faced with choices about how to respond when a resource becomes depleted. We hypothesise that flying insects like bees discover new food sources using an optimal Lévy flight searching strategy and odour-mediated anemotaxis, as well as visual cues. To study these searching patterns, foraging honeybees were trained to a scented feeder which was then removed. Two new unrewarding feeders, or ‘targets’, were then positioned up- and downwind of the original location of the training feeder. The subsequent flight patterns of the bees were recorded over several hundred metres using harmonic radar. We show that the flight patterns constitute an optimal Lévy flight searching strategy for the location of the training feeder, a strategy that is also optimal for the location of alternative food sources when patchily distributed. Scented targets that were positioned upwind of the original training feeder were investigated most with the numbers of investigations declining with increasing distance from the original feeder. Scented targets in downwind locations were rarely investigated and unscented targets were largely ignored, despite having the same visual appearance as the rewarding training feeder.