It is an open question how animals find food in dynamic natural environments where they possess little or no knowledge of where resources are located. Foraging theory predicts that in environments with sparsely distributed target resources, where forager knowledge about resources' locations is incomplete, Lévy flight movements optimize the success of random searches. However, the putative success of Lévy foraging has been demonstrated only in model simulations. Here, we use high-temporal-resolution Global Positioning System (GPS) tracking of wandering (Diomedea exulans) and black-browed albatrosses (Thalassarche melanophrys) with simultaneous recording of prey captures, to show that both species exhibit Lévy and Brownian movement patterns. We find that total prey masses captured by wandering albatrosses during Lévy movements exceed daily energy requirements by nearly fourfold, and approached yields by Brownian movements in other habitats. These results, together with our reanalysis of previously published albatross data, overturn the notion that albatrosses do not exhibit Lévy patterns during foraging, and demonstrate that Lévy flights of predators in dynamic natural environments present a beneficial alternative strategy to simple, spatially intensive behaviors. Our findings add support to the possibility that biological Lévy flight may have naturally evolved as a search strategy in response to sparse resources and scant information.