We study a random walk on a point process given by an ordered array of points $(ω_k, \, k \in \mathbb{Z})$ on the real line. The distances $ω_{k+1} - ω_k$ are i.i.d. random variables in the domain of attraction of a $β$-stable law, with $β\in (0,1) \cup (1,2)$. The random walk has i.i.d. jumps such that the transition probabilities between $ω_k$ and $ω_\ell$ depend on $\ell-k$ and are given by the distribution of a $\mathbb{Z}$-valued random variable in the domain of attraction of an $α$-stable law, with $α\in (0,1) \cup (1,2)$. Since the defining variables, for both the random walk and the point process, are heavy-tailed, we speak of a Lévy flight on a Lévy random medium. For all combinations of the parameters $α$ and $β$, we prove the annealed functional limit theorem for the suitably rescaled process, relative to the optimal Skorokhod topology in each case. When the limit process is not càdlàg, we prove convergence of the finite-dimensional distributions. When the limit process is deterministic, we also prove a limit theorem for the fluctuations, again relative to the optimal Skorokhod topology.