An influential study a decade ago concluded that wandering albatrosses (Diomedea exulans) perform Lévy flights when searching for prey on the ocean surface (Nature 381:413-415, 1996). Lévy flights are random walks whose step lengths come from probability distributions that have heavy power-law tails. They display fractal properties and have no typical scale. A follow-up study concluded that deer (Dama dama) and bumblebees (Bombus terricola) also perform Lévy flights (Nature 401:911-914, 1999). These pioneering studies have motivated a large body of theoretical work, as well as empirical work conerning, for example, reindeer, microzooplankton, grey seals, spider monkeys and fishing boats. Here we analyze a new, high-resolution data set of wandering albatross flights, and find no evidence for Lévy flights. Rather, the flight times are gamma distributed, with a simple exponential decay for the longest flights. We re-analyse the data set used in the original albatross study and find that the extremely long flights essential for demonstrating Lévy flight behaviour actually represented time that the birds spent sitting on their nests. We develop a likelihood method and use Akaike weights to re-analyze the four original deer and bumblebee data sets, and show that none of them exhibit evidence of Lévy flights. Furthermore, the log-log histogram method originally used to ascertain Lévy flight behaviour is not rigorous and yields misleading results. This method has since been widely adopted to conclude Lévy flight movement for other organisms, and to propose that Lévy flight analysis might have potential as a real-time ecosystem monitoring tool. However, our results question the Lévy flight paradigm as a suitable model of search behaviour.