republiky sa z domácej linky do Prahy automaticky stala medzinárodná linka.

Prvou novozavedenou zahraničnou linkou, spájajúcou Košice s inou než "československou" destináciou, sa stala linka Viedeň-Košice-Viedeň, ktorú rakúske aerolínie Tyrolean Airways otvorili 15. apríla 1996. Na linke medzi Viedňou a Košicami lietali lietadlá Tyrolean Airways spočiatku dva razy týždenne, a to v utorok a štvrtok. V apríli 1998 sa frekvencia letov rozšírila tak, že z Viedne do Košíc sa lietal každý deň okrem soboty a nedele. Od októbra 1998 sa na uvedenej linke začalo lietať aj v nedeľu. V októbri 2003 pribudla k existujúcim denným linkám druhá linka, a to s večerným príletom do Košíc a odletom do Viedne nasledujúci skoro ráno. Linky sú v súčasnosti uvádzané v letovom poriadku pod hlavičkou spoločnosti Austrian Airlines (AUA), ktorá je od 23. marca 1998 stopercentným vlastníkom Tyrolean Airways. V súčasnosti spájajú lietadlá AUA Košice s Viedňou 22 razy týždenne (11 párov letov). Od začatia prevádzky do marca tohto roku bolo na linke Viedeň-Košice resp. Košice-Viedeň prepravených spolu temer 121 000 cestujúcich. Za 10 rokov trvania linky pristáli lietadlá AUA v Košiciach 2 500 ráz. Na linke z Viedne do Košíc lietajú zväčša turbovrtuľové lietadlo Bombardier Dash 8/300Q kanadskej výroby (na snímke), ale na tejto linke boli nasadené aj prúdové lietadlá Bombardier CRJ 100ER/200ER i turbovrtuľové lietadlá Fokker 50/70. Let z Viedne do Košíc či naopak trvá v priemere len 50 minút.