Kao dio planova za restrukturiranje tvrtke, Grčka kasne 2003. osniva Olympic Airlines. Nova tvrtka preuzela je poslove prijevoza i većinu imovine Olympic Airwaysa, ostavljajući za sobom gotovo sve dugove.
Si pjesë e planeve të veta për të ristrukutruar kompaninë, Greqia krijoi Olympic Airlines në fund të vitit 2003, duke lënë pas pothuajse të gjitha borxhet e saj.