A new structure for adaptive AR spectral estimation based on multi-band decomposition of the linear prediction error is introduced and the mathematical background for the soulution of the related adaptive filtering problem is derived. The presented structure gives rise to AR spectral estimates that represent the true underlying spectrum with better fidelity than conventional LS methods by allowing an arbitrary trade-off between variance of spectral estimates and tracking ability of the estimator along the frequency spectrum. The linear prediction error is decomposed through a filter bank and components of each band are analyzed by different window lengths, allowing long windows to track slowly varying signals and short windows to observe fastly varying components. The correlation matrix of the input signal is shown to satisfy both time-update and order-update properties for rectangular windowing functions, and an RLS algorithm based on each property is presented. Adaptive forward and backward relations are used to derive a mathematical framework that serves as a basis for the design of fast RLS alogorithms. Also, computer experiments comparing the performance of conventional and the proposed multi-band methods are depicted and discussed.