Nearly zero energy buildings (NZEBs) constitute one of the main pillars of the energy policy of European Union (EU). Greece has recently established a clear definition for NZEB, however the interdependence between cost-optimality and the energy performance of NZEB has not been adequately studied. The present work includes a cost effectiveness analysis among different energy efficiency interventions for the existing residential Greek building stock. To this end, the calculation of the investment as well as the operating and maintenance cost for a wide range of energy efficiency measures were carried out. All calculations were based on the methodology defined in the Directive 2010/31/EU on the energy performance of buildings, while the economic evaluation assumptions were based on the EN 15459-1 standard. The goal is the determination of the most cost effective (cost-optimal) measures that are applicable for two different building types; Single Family House (SFH) buildings and Multi-family House (MFH) apartment blocks, taking into account the period of their construction and the climate zone they belong to. Furthermore, the scope of the paper includes also the assessment of the gap between these measures and the NZEB thresholds. The analysis showed that in various cases and depending on the exact national NZEB definition, NZEBs are located beyond cost optimality.