This paper presents EvoNFuzz, a novel Evolutionary Neuro-Fuzzy Network that integrates functional fuzzy rules with a hybrid learning approach combining Multi-Gene Genetic Programming (MGGP) and gradient-based optimization. Unlike traditional Takagi-Sugeno models, EvoNFuzz employs polynomial-based consequents, evolved via MGGP, to more effectively capture complex non-linear relationships in data. Additionally, EvoNFuzz incorporates rule weights akin to those in neural networks, allowing it to assign varying degrees of importance to each fuzzy rule. The membership functions are determined using the K-Means clustering algorithm. A Gradient-based learning algorithm adjusts the rule weights and the membership functions. The performance of EvoNFuzz is rigorously tested against alternative models on non-linear regression tasks. The computational results demonstrate that EvoNFuzz consistently outperforms or matches the performance of alternative models.