The decision function of the LS-SVM is often spanned by all the training samples, which is known as the issue of non-sparsity. This paper proposes a new recursive learning algorithm, selecting one training sample into the decision function at one time. The proposed algorithm first selects the training sample which minimizes the sum of squared loss for the linear regression model associated with the LS-SVM. At each of the subsequent iterations, the algorithm identifies and selects the training sample yielding a classifier which performs the best on those unselected training samples. For the update of the parameter vector of the LS-SVM due to addition of an extra training sample into the solution, it is demonstrated that the parameter vector can be derived without explicit inversion of the coefficient matrix of the linear system associated with the LS-SVM. This approach greatly reduces the computational complexity of the proposed algorithm. Experimental results on the checkerboard dataset demonstrated the proposed LS-SVM, parameterized by a smaller number of training samples than the standard LS-SVM, can recognize the checkerboard pattern accurately. The proposed LS-SVM model also demonstrated generalization performances superior to other sparse models on five datasets from the UCI repository.