In this paper, a correntropy-based evolving fuzzy neural system (CEFNS) is proposed for approximation of nonlinear systems. Different from the commonly used mean-square error criterion, correntropy has a strong outliers rejection ability through capturing the higher moments of the error distribution. Considering the merits of correntropy, this paper brings contributions to build evolving fuzzy neural system (EFNS) based on the correntropy concept to achieve a more stable evolution of the rule base and update of the rule parameters instead of the commonly used mean-square error criterion. The correntropy-EFNS (CEFNS) begins with an empty rule base, and all rules are evolved online based on the correntropy criterion. The consequent part parameters are tuned based on the maximum correntropy criterion, where the correntropy is used as the cost function so as to improve the non-Gaussian noise rejection ability. The steady-state convergence performance of the CEFNS is studied through the calculation of the steady-state excess mean square error (EMSE) in two cases: Gaussian noise; and non-Gaussian noise. Finally, the CEFNS is validated through a benchmark system identification problem, a Mackey-Glass time series prediction problem as well as five other real-world benchmark regression problems under both noise-free and noisy conditions. Compared with other EFNSs, the simulation results show that the proposed CEFNS produces better approximation accuracy using the least number of rules and training time and also owns superior non-Gaussian noise handling capability.