We develop an excursion theory that describes the evolution of a Markov process indexed by a Levy tree away from a regular and instantaneous point $x$ of the state space. The theory builds upon a notion of local time at $x$ that was recently introduced in [37]. Despite the radically different setting, our results exhibit striking similarities to the classical excursion theory for $\mathbb{R}_+$-indexed Markov processes. We then show that the genealogy of the excursions can be encoded in a Levy tree called the tree coded by the local time. In particular, we recover by different methods the excursion theory of Abraham and Le Gall [2], which was developed for Brownian motion indexed by the Brownian tree.