A classic method for computing the mass function of dark matter halos is provided by excursion set theory, where density perturbations evolve stochastically with the smoothing scale, and the problem of computing the probability of halo formation is mapped into the so-called first-passage time problem in the presence of a barrier. While the full dynamical complexity of halo formation can only be revealed through N-body simulations, excursion set theory provides a simple analytic framework for understanding various aspects of this complex process. In this series of paper we propose improvements of both technical and conceptual aspects of excursion set theory, and we explore up to which point the method can reproduce quantitatively the data from N-body simulations. In paper I of the series we show how to derive excursion set theory from a path integral formulation. This allows us both to derive rigorously the absorbing barrier boundary condition, that in the usual formulation is just postulated, and to deal analytically with the non-markovian nature of the random walk. Such a non-markovian dynamics inevitably enters when either the density is smoothed with filters such as the top-hat filter in coordinate space (which is the only filter associated to a well defined halo mass) or when one considers non-Gaussian fluctuations. In these cases, beside ``markovian terms, we find ``memory terms that reflect the non-markovianity of the evolution with the smoothing scale. We develop a general formalism for evaluating perturbatively these non-markovian corrections, and in this paper we perform explicitly the computation of the halo mass function for gaussian fluctuations, to first order in the non-markovian corrections due to the use of a tophat filter in coordinate space.