A theoretical framework describing the hydrodynamic interactions between a passive particle and an active medium in out-of-equilibrium systems predicts long-range Levy flights for the diffusing particle driven by the density of the active component. Brownian motion is widely used as a model of diffusion in equilibrium media throughout the physical, chemical and biological sciences. However, many real-world systems are intrinsically out of equilibrium owing to energy-dissipating active processes underlying their mechanical and dynamical features(1). The diffusion process followed by a passive tracer in prototypical active media, such as suspensions of active colloids or swimming microorganisms(2), differs considerably from Brownian motion, as revealed by a greatly enhanced diffusion coefficient(3-10) and non-Gaussian statistics of the tracer displacements(6,9,10). Although these characteristic features have been extensively observed experimentally, there is so far no comprehensive theory explaining how they emerge from the microscopic dynamics of the system. Here we develop a theoretical framework to model the hydrodynamic interactions between the tracer and the active swimmers, which shows that the tracer follows a non-Markovian coloured Poisson process that accounts for all empirical observations. The theory predicts a long-lived Levy flight regime(11) of the loopy tracer motion with a non-monotonic crossover between two different power-law exponents. The duration of this regime can be tuned by the swimmer density, suggesting that the optimal foraging strategy of swimming microorganisms might depend crucially on their density in order to exploit the Levy flights of nutrients(12). Our framework can be applied to address important theoretical questions, such as the thermodynamics of active systems(13), and practical ones, such as the interaction of swimming microorganisms with nutrients and other small particles(14) (for example, degraded plastic) and the design of artificial nanoscale machines(15).