Summary: We propose and investigate a new category of neurofuzzy networks – Fuzzy Polynomial Neural Networks (FPNN) endowed with Fuzzy Set-based Polynomial Neurons (FSPNs) We develop a comprehensive design methodology involving mechanisms of genetic optimization, and Genetic Algorithms (GAs) in particular. The conventional FPNNs developed so far are based on the mechanisms of self-organization, fuzzy neurocomputing, and evolutionary optimization. The design of the network exploits the FSPNs as well as the extended Group Method of Data Handling (GMDH). Let us stress that in the previous development strategies some essential parameters of the networks (such as the number of input variables, the order of the polynomial, the number of membership functions, and a collection of the specific subset of input variables) being available within the network are provided by the designer in advance and kept fixed throughout the overall development process. This restriction may hamper a possibility of developing an optimal architecture of the model. The design proposed in this study addresses this issue. The augmented and genetically developed FPNN (gFPNN) results in a structurally optimized structure and comes with a higher level of flexibility in comparison to the one we encounter in the conventional FPNNs. The GA-based design procedure being applied at each layer of the FPNN leads to the selection of the most suitable nodes (or FSPNs) available within the FPNN. In the sequel, two general optimization mechanisms are explored. First, the structural optimization is realized via GAs whereas the ensuing detailed parametric optimization is carried out in the setting of a standard least square method-based learning. The performance of the gFPNN is quantified through experimentation in which we use a number of modeling benchmarks–synthetic and experimental data being commonly used in fuzzy or neurofuzzy modeling. The obtained results demonstrate the superiority of the proposed networks over the models existing in the references.