In this article, a novel approach for assessment and ranking of maintenance process indicators as well as maintenance cost indicators and maintenance equipment indicators using the fuzzy sets approach and genetic algorithms is presented. Weight values of these indicators are defined using the experience of decision makers from analyzed small and medium enterprises (total number of 197 persons) and calculated using the fuzzy sets approach. In the second step, a model for ranking and optimization of maintenance performance indicators and small and medium enterprises by using genetic algorithm is presented. The presented approach enables multi-objective optimization of selected key performance indicators in the scope of optimization of maintenance performances. The value of optimization was tested on a group of small and medium enterprises which proved that improvement of maintenance performance could be more significant (or performed at the shorter period of time) if the specific key performance indicators were targeted for improvement. The presented solution could provide identification of strengths and weaknesses (comparing key performance indicators), learning from a leading organization (in prioritization of key performance indicator improvement) and improvement of maintenance performance.