In this paper we propose a new algorithm to solve large Toeplitz systems. It consists of two steps. First, we embed the system of order N into a semi-infinite Toeplitz system and compute the first N components of its solution by an algorithm of complexity O(N log2 N). Then we check the accuracy of the approximate solution, by an a posteriori criterion, and update the inaccurate components by solving a small Toeplitz system. The numerical performance of the method is then compared with the conjugate gradient method, for 3 different preconditioners. It turns out that our method is compatible with the best PCG methods concerning the accuracy and superior concerning the execution time.