The paper presents energy performance and environmental impact analysis of cost-optimal renovation solutions conducted in deep renovations of typical large panel-structured apartment buildings located in cold climate conditions. The main objective of the study was to determine the cost-optimal renovation concepts from both the primary energy performance and the total CO2 emission reduction potential perspectives. The cost-optimal solutions for different main heating systems were determined from over 220 million renovation combinations by using a simulation-based multi-objective optimization (SBMOO) analysis as the main research method. The results demonstrate that the proposed national nearly zero-energy apartment building level can be cost-effectively achieved in deep renovations of large panel apartment buildings, delivering approximately 18–36% return on investment. The results also indicate that up to 90–98 €/m2 net savings, 850–930 kWh/m2 reduction in the primary energy consumption and 350–390 kg/m2 reduction in the total CO2 emissions over the studied 30-year life-cycle period can be achieved simultaneously, when the cost-optimal renovation concepts are selected. Cost-optimally dimensioned heat pump systems deliver significant cost saving and environmental impact reduction potential compared to improving the energy efficiency of the building envelope, as the delivered energy consumption accounts for more than 90% of the total CO2 emissions.