Lévy walks as a random search strategy have recently attracted a lot of attention, and have been described in many animal species. However, very little is known about one of the most important issues, namely how Lévy walks are generated by biological organisms. We study a model of the chemotaxis signaling pathway of E. coli, and demonstrate that stochastic fluctuations and the specific design of the signaling pathway in concert enable the generation of Lévy walks. We show that Lévy walks result from the superposition of an ensemble of exponential distributions, which occurs due to the shifts in the internal enzyme concentrations following the stochastic fluctuations. With our approach we derive the power-law analytically from a model of the chemotaxis signaling pathway, and obtain a power-law exponent μ ≈ 2.2, which coincides with experimental results. This work provides a means to confirm Lévy walks as natural phenomenon by providing understanding on the process through which they emerge. Furthermore, our results give novel insights into the design aspects of biological systems that are capable of translating additive noise on the microscopic scale into beneficial macroscopic behavior.