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 papers 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 with 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 top-hat filter in coordinate space. In Paper II of this series we propose to extend excursion set theory by treating the critical threshold for collapse as a stochastic variable, which better captures some of the dynamical complexity of the halo formation phenomenon, while in Paper III we use the formalism developed in this paper to compute the effect of non-Gaussianities on the halo mass function.