Measure the performance of maintenance service and the influence of implemented practices in maintenance activities is essential to the success of companies. Maintenance managers deal with the complex tasks of find out the best maintenance performance indicators which can help them in achieve goals. In this chapter a new approach is introduced for maintenance Key Performance Indicators (KPIs) selection using the original ELECTRE I, which is a Multi Criteria Decision Making method. This chapter describes the methodology of the decision model and a case study to exemplify its use is presented. The proposed methodology determines a ranking of possible alternatives after its evaluations according important criteria. The proposed methodology that involves decision maker’s preference information makes the decision process more explicit, rational and efficient. Light to the results, this chapter proves that the new methodology is an effective tool to assist maintenance managers in accurate KPIs selection tasks in line with maintenance objectives and strategies.