Tracking and adaptation algorithms are, from a formal point of view, nonlinear systems which depend on stochastic variables in a fairly complicated way, The analysis of such algorithms is thus quite complicated, A first step is to establish the exponential stability of these systems, This is of interest in its own right and a prerequisite for the practical use of the algorithm, It is also a necessary starting point to analyze the performance in terms of tracking and adaptation because that is how close the estimated parameters are to the time-varying true ones. In this contribution we establish some general conditions for the exponential stability of a wide and common class of tracking algorithms, This includes least mean squares, recursive least squares, and Kalman filter based adaptation algorithms, We show how stability of an averaged (linear and deterministic) equation and stability of the actual algorithm are linked to each other under weak conditions on the involved stochastic processes, We also give explicit conditions for exponential stability of the most common algorithms, The tracking performance of the algorithms is studied in a companion paper.