Nurse scheduling problem (NSP) is one of the most popular constraint satisfaction problems and its importance is very high to maintain high quality medical services and avoid staff's work overload in real world. Even though there are some commercial scheduling software for calculating optimal assignment of shifts and holidays to nurses, these haven't met user's demand yet in the points of computational time and diversity of candidate schedulings. Since it is widely known that the constraints of NSP can be categorized into two main types; nursing quality and staff's quality of life, NSP can be treated as two-objective optimization problem. In this paper, a new approach for NSP is proposed. The proposed approach is based on evolutionary multi-criterion optimization (EMO) and its main features are high search performance and derivation of plural different candidate solutions. This research is collaboration with System Bank Co.,Ltd. and its mission is to improve an existing optimization engine. To investigate the characteristics and effectiveness of the proposed approach, the proposed is applied to three different benchmark problems which have characters and difficulty levels. The results of numerical examples provided that the performance of the proposed approach is overwhelming in comparison with the existing engine in every problems. Also, each mechanism's works of the proposed approach can be apparent through numerical examples.