Conventional face recognition suffers from problems such as extending the classifier for newly added people and learning updated information about the existing people. The way to address these problems is to retrain the system which will require expensive computational complexity. In this paper, a radial basis function (RBF) neural network with a new incremental learning method based on the regularized orthogonal least square (ROLS) algorithm is proposed for face recognition. It is designed to accommodate new information without retraining the initial network. In our proposed method, the selection of the regressors for the new data is done locally, hence avoiding the expensive reselecting process. In addition, it accumulates previous experience and learns updated new knowledge of the existing groups to increase the robustness of the system. The experimental results show that the proposed method gives higher average recognition accuracy compared to the conventional ROLS-algorithm-based RBF neural network with much lower computational complexity. Furthermore, the proposed method achieves higher recognition accuracy as compared to other incremental learning algorithms such as incremental principal component analysis and incremental linear discriminant analysis in face recognition.