This paper presents a methodology, using Life Cycle Cost (LCC) optimization and building categorization, to achieve a systematic study of the cost-optimal energy efficiency potential (CEEP) for 920 listed buildings in the medieval district of Visby in Sweden. The aim is to study the CEEP and CO2 emission reductions for this city that is included in the World Heritage List by UNESCO. The total CEEP is found to be 31% (20.6 GWh) resulting in a CO2 reduction of 57% (33.3 kton). The categorization method showed that the buildings could be divided in four clusters depending on building material, geometry and layout. The LCC analysis revealed that the energy efficiency measure packages were cluster specific. It is shown that multi-story wood buildings (Cluster II) have lowest specific LCC, and would arguably be the starting point for a renovation process. Presently most of the studied buildings are connected to the district heating (DH). The results show that heat pump (HP) and wood boiler (WB) is cost-optimal heating system for multi-story stone and wood buildings, respectively. In order for the DH to compete with HP and WB, the DH price needs to be reduced by 23% and 16%.