Turkish Airlines jsou horkým favoritem stát se národním dopravce Republiky Makedonie. Turecký dopravce v současnosti létá 2x denně do Skopje (typy Boeing 737-700 a Airbus 319) a hovoří pro něj také fakt, že turecká společnost TAV je majoritní akcionář makedonských letišť Skopje a Ohrid. V případě úspěchu by Turkish bázovali několik letadel ve Skopje. Dopravce vybírá makedonská vláda již několik let po bankrotu MAT Airways. Ty byly založeny v roce 1994 jako Macedonian Air Transport a zahájili provoz s jedním 
Boeing 737-200 (pronajatým od Egyptairu). Jejich flotila byla velmi pestrá pronajímaly si postupně letadla různých typů od různých společností: Tupolev 154 (od Estonského ELKu)Jakovlev 42 (od Saravie), McDonnell Douglas MD-81, Douglas DC-9 (od srbského JATu)Boeing 737-300 (od srbského JATu),  Boeing 737-500 Embraer 170Bombardier CRJ-900. Krátký čas létaly pravidelně i do Prahy typem DC-9. MAT Airways zbakrotovaly v roce 2011.