Classification is inherently multi-objective problem. It is one of the most important tasks of data mining to extract important patterns from large volume of data. Traditionally, either only one objective is considered or the multiple objectives are accumulated to one objective function. In the last decade, Pareto-based multi-objective optimization approach have gained increasing popularity due to the use of multi-objective optimization using evolutionary algorithms and population-based search methods. Multi-objective optimization approaches are more powerful than traditional single-objective methods as it addresses various topics of data mining such as classification, clustering, feature selection, ensemble learning, etc. This paper proposes improved approach of non-dominated sorting algorithm II (NSGA II) for classification using neural network model by augmenting with local search. It tries to enhance two conflicting objectives of classifier: Accuracy and mean squared error. NSGA II is improved by augmenting backpropagation as a local search method to deal with the disadvantage of genetic algorithm, i.e. slow convergence to best solutions. By using backpropagation we are able to speed up the convergence. This approach is applied in various classification problems obtained from UCI repository. The neural network modes obtained shows high accuracy and low mean squared error. © Springer Science+Business Media Singapore 2016.