In a recent work [7], some general results on exponential stability of random linear equations are established which can be applied directly to the performance analysis of a wide class of adaptive algorithms, including the basic LMS ones, without requiring stationarity, independency, and boundedness assumptions of the system signals, The current paper attempts to give a complete characterization of the exponential stability of the LMS algorithms by providing a necessary and sufficient condition for such a stability in the case of possibly unbounded, nonstationary, and non-phi-mixing signals, The results of this paper can be applied to a very large class of signals, including those generated from, e.g., a Gaussian process via a time-varying linear filter. As an application, several novel and extended results on convergence and the tracking performance of LMS are derived under various assumptions, Neither stationarity nor Markov-chain assumptions are necessarily required in the paper.