In 2022, further municipal elections await us, for the first time connected with elections to the bodies of higher territorial units (self-governing regions). This paper aims to evaluate the issue of elections of mayors in Slovakia in a longer period of time (2002-2018), in terms of the degree of legitimacy regarding the power of this post with respect to the size categories of municipalities by population and related election results. In the study, we work with nine size categories, in the case of the two largest cities (Bratislava and Košice) also separately. In addition, the issue is assessed at the local level - at the level of municipalities forming clusters within the territory of Slovakia on the basis of a similar degree of legitimacy, using the concept of spatial autocorrelation. For this purpose, an index evaluating legitimacy of power was constructed consisting of three components taking into account the level of electoral support, turnout and competition. As an additive indicator, in the case of individual size categories of municipalities we present the intensity of changes in the position of mayor in the municipal elections since 2002. Higher legitimacy of the office has been identified in the case of smaller municipalities, but it is declining over time. On the contrary, the urban environment is characterized by a lower degree of legitimacy, but with a positive outlook (the trend of strengthening the legitimacy of the mayor's post). However, the development of the values concerning the individual components of the index is considerably divergent over time when comparing different municipal size categories.