A new neuro-fuzzy computing paradigm using complex fuzzy sets is proposed in this paper. The novel computing paradigm is applied to the problem of function approximation to test its nonlinear mapping ability. A complex fuzzy set (CFS) is an extension of traditional type-1 fuzzy set whose membership is within the unit real-valued interval. For a CFS, the membership is extended to complex-valued state within the unit disc of the complex plane. For self-adaption of the proposed complex neuro-fuzzy system (CNFS), the Particle Swarm Optimization (PSO) algorithm and Recursive Least Squares Estimator (RISE) algorithm are used in a hybrid way to adjust the free parameters of the CNFS. With the novel PSO-RLSE hybrid learning method, the CNFS parameters can be converged efficiently and quickly. By the PSO-RLSE method for the CNFS, fast learning convergence is observed and great performance in accuracy is shown. In the experimental results, the CNFS shows much better performance than its traditional neuro-fuzzy counterpart and other compared approaches. Excellent performance by the proposed approach has been shown.