One of the most influential factors in the quality of the solutions found by an evolutionary algorithm is the appropriateness of the fitness function. Specifically in data mining, in where the extraction of useful information is a main task, when databases have a great amount of examples, fitness functions are very time consuming. In this sense, an approximation to fitness values can be beneficial for reducing its associated computational cost. In this paper, we present the Neural-Evolutionary Model (NEM), which uses a neural network as a fitness function estimator. The neural network is trained through the evolutionary process and used progressively to estimate the fitness values, what enhances the search efficiency while alleviating the computational overload of the fitness function. We demonstrate that the NEM is faster than the traditional evolutionary algorithm, under some assumptions over the total amount of estimations carried out by the neural network. The Neural-Evolutionary Model proves then useful when datasets contain vast amount of examples. © Springer-Verlag Berlin Heidelberg 2003.