Ever since European Directive 2012/27/EU, particular attention has been focused on the improvement of the energy efficiency of the public building stock. According to the directive, local public authorities, regions and municipalities, are expected to develop and implement energy efficiency retrofitting plans for their public building stocks. While conducting such plans, important challenges are raised mainly related to data collection and the manipulation of key performance indicators (KPIs) for many buildings. The present paper deals with the aforementioned challenges through (a) the evaluation of freely available tools developed in the framework of Mediterranean territorial cooperation projects, with respect to the main pillars of energy efficiency planning, and (b) the introduction of a stepwise methodology using selected tools toward a reliable energy efficiency plan extending from the classification of the building stock to the prioritization of projects in terms of a gradual renovation plan based on energy and cost criteria. The methodology is applied for a case study in Greece, which refers to 10 public buildings of the Municipality of Aigialeia in Greece. A reliable renovation plan is developed, taking into account the municipal authority’s directions in a specialized decision-making scheme. It is concluded that the suggested methodology is very practical for planning purposes, while for the case studied, a 6-year gradual renovation plan is emerged until a deep retrofit of all buildings, associated with an estimated primary energy saving and CO2 emissions avoidance of more than 1850 MWh and 400 tns, respectively, with a total investment of about EUR 3 million.