This paper presents a self-evolving kernel recursive least squares (KRLS) algorithm which implements the modelling of unknown nonlinear systems in reproducing kernel Hilbert spaces (RKHS). The prime motivation of this development is a reformulation of the well known KRLS algorithm which inevitably increases the computational complexity to the cases where data arrive sequentially. The self-evolving KRLS algorithm utilizes the measurement of kernel evaluation and adaptive approximation error to determine the learning system with a structure of a suitable size that involves recruiting and dimension reduction of the kernel vector during the adaptive learning phase without predefining them. This self-evolving procedure allows the algorithm to operate online, often in real time, reducing the computational time and improving the learning performance. This algorithm is finally utilized in the applications of online adaptive control and time series prediction where the system is described as a unknown function by Nonlinear AutoRegressive with Exogenous inputs model. Simulation results from an inverted pendulum system and Time Series Data Library demonstrate the satisfactory performance of the proposed self-evolving KRLS algorithm.