This paper present a Non-dominated Sorting based Multi Ob- jective A ∗ Search (NSMOA ∗ ) algorithm for multi-objective search prob- lem. It is an extension of the New Approach for Multi Objective A ∗ Search (NAMOA ∗ ). This study aims to improve the selection phase of the NAMOA ∗ algorithm which can affect the performance of the algorithm considerably, especially when the number of non-dominated solutions in- creases to a large number during the search. This research proposes a new sorting method that allows selection and expansion of the partial solutions be carried out more efficiently. The results demonstrate that our algorithm expands fewer nodes and explores a smaller region of solution space using the same heuristic.