A new recursive algorithm is introduced to adjust the parameters of an adaptive channel equalizer based on the use one cycle Successive Over-Relaxation (SOR) iteration between two consecutive data samples. The presented algorithm is called the Recursive Successive Over-Relaxation (RSOR) algorithm. In addition, a stochastic convergence analysis of the RSOR algorithm is performed and it is shown that the proposed algorithm is an unbiased parameter estimator for optimum Wiener solution of normal equation. The performance of the RSOR algorithm in terms of its convergence rate and computational complexity is examined using computer simulations and compared with the widely used adaptive algorithms. The computer simulations show that the proposed algorithm has a faster convergence rate than the gradient-based methods and a lower computational complexity than the Recursive Least Squares (RLS) algorithm.