The article is devoted to the problem of assessing the effectiveness of executives in the regions of Russia, based on the example of the North Caucasus Federal District republics. They often appear among the lagging subsidized subjects of the Russian Federation, with low industry, high fertility, high unemployment, and other socio-economic challenges for administration. The government effectiveness can be viewed from different points: 1) from the angle of the implementation of their social functions by the authorities; 2) understanding efficiency as the correlation of societal demands towards the system, and the authorities’ decisions; and 3) in terms of the quality of state and legal institutions that promote efficiency. The program-targeted approach and the digitalization of the economy pose new challenges to improve the quality of governance and the provision of public services, and to provoke a change in regulatory framework. The article studies the list of indicators of the regional executive functioning, introduced by the Decree of the President of Russia and adopted in April 2019. Comparing the new indicators with the previous assessment system, the author analyzes the socio-economic statistics data of the North Caucasus republics and shows their applicability to the assessment of the regional governance. Particular attention is paid to the indicator “trust in power”, which replaced the previous indicator of the population’s social satisfaction. The article offers ways to optimize the methodology and criteria for measuring the effectiveness of power.