Brownian motion is widely used as a paradigmatic model of diffusion in equilibrium media throughout the physical, chemical, and biological sciences. However, many real world systems, particularly biological ones, are intrinsically out-of-equilibrium due to the energy-dissipating active processes underlying their mechanical and dynamical features. The diffusion process followed by a passive tracer in prototypical active media such as suspensions of active colloids or swimming microorganisms indeed differs significantly from Brownian motion, manifest in a greatly enhanced diffusion coefficient, non-Gaussian tails of the displacement statistics, and crossover phenomena from non-Gaussian to Gaussian scaling. While such characteristic features have been extensively observed in experiments, there is so far no comprehensive theory explaining how they emerge from the microscopic active dynamics. Here we present a theoretical framework of the enhanced tracer diffusion in an active medium from its microscopic dynamics by coarse-graining the hydrodynamic interactions between the tracer and the active particles as a stochastic process. The tracer is shown to follow a non-Markovian coloured Poisson process that accounts quantitatively for all empirical observations. The theory predicts in particular a long-lived Levy flight regime of the 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, thus suggesting that the optimal foraging strategy of swimming microorganisms might crucially depend on the density in order to exploit the Levy flights of nutrients. Our framework provides the first validation of the celebrated Levy flight model from a physical microscopic dynamics.