Rakúska letecká spoločnosť Austrian Airlines (AUA) získala v rámci navyšovania kapitálu 62-% podiel v Slovenských aerolíniách (SA).

SA vznikli vo forme akciovej spoločnosti s pôvodným základným kapitálom 1,3 milióna Sk, s podielom štátu 34,4 % a spoločnosti Devín Group, s. r. o., 33,5 %, zodpovednej za správu splátok ruského dlhu voči Slovensku. Ďalšími zakladajúcimi akcionármi boli Wili, a. s., s podielom 28,9 % a ruský konštrukčný podnik OKB Jakovlev, vtedy s 3,2-% podielom. Štát poskytol SA ruské lietadlá TU 154M, ktoré získal ako súčasť splátok ruských dlhov voči Slovensku.

Slovensko sa snažilo založiť národného leteckého dopravcu od roku 1993, keď sa rozdelila bývalá Česká a Slovenská federatívna republika. Česká republika vtedy získala úplnú kontrolu (vrátane ich leteckého parku) nad Československými aerolíniami (ČSA), ktoré sa premenovali na České aerolínie a ďalej používajú značku ČSA.

SA žiadali o osvedčenie leteckého prevádzkovateľa od roku 1996. Napriek tomu, že nespĺňali podmienky leteckého dopravcu, lebo nevlastnili nijaké lietadlo, Ministerstvo dopravy, pôšt a telekomunikácií (MDPT) SR im 19. decembra 1996 vydalo osvedčenie leteckého prevádzkovateľa a povolenie na vykonávanie leteckej dopravy, podmienečne na jeden rok.

SA nakoniec z deblokácie pohľadávok SR voči Ruskej federácii získali tri lietadlá. Na bratislavskom Letisku Milana Rastislava Štefánika pristál 16. januára 1998 prvý z troch Tupolevov pre SA T 154 M. Prvá pravidelná letecká linka SA začala lietať 1. mája 1998 na trase Bratislava - Moskva, ktorú s prestávkami prevádzkuje doteraz. V dovolenkovom období jún-september začala spoločnosť prevádzkovať prvé charterové linky, ktoré sa v nasledujúcich rokoch stali dôležitou súčasťou jej príjmov. Onedlho na to, 10. augusta 1998, otvorila pravidelnú leteckú linku Bratislava - Košice, ktorej prevádzku viackrát prerušila. V súčasnosti SA túto destináciu nelieta.

V Bratislave sa 14. augusta 1998 uskutočnilo mimoriadne valné zhromaždenie akcionárov SA. Účastníci rokovania zvolili nové zloženie orgánov spoločnosti. Predsedom predstavenstva sa stal Štefan Nemeš a za predsedu dozornej rady bol zvolený Viliam Veteška.

Ešte v priebehu roku 1998 otvorili SA pravidelnú sezónnu linku Poprad - Moskva, ktorá v súčasnosti už nie je v prevádzke.

Po parlamentných voľbách MDPT, sekcia civilného letectva, 16. novembra 1998 dočasne odobrala povolenie na vykonávanie leteckej dopravy za úhradu leteckej spoločnosti SA. Uvedený orgán štátnej moci pritom dospel po zistení skutkového stavu veci k záveru, že v spoločnosti SA pretrvávajú z hľadiska vykonávania leteckej dopravy dlhodobé problémy, z ktorých vyplýva odôvodnené podozrenie z porušenia právnych predpisov SR.

Po spoločnom rokovaní 19. novembra 1998 zástupcovia MDPT a SA uzatvorili dohodu, podľa ktorej majú obe strany záujem o vyriešenie vzniknutého problému a budú koordinovať svoj postup v záujme ďalšieho rozvoja leteckej dopravy na Slovensku.

Následne 15. januára 1999 malo dôjsť na Letisku M.R. Štefánika v Bratislave k pokusu o zabavenie troch lietadiel TU 154-M, ktoré štát prenajal spoločnosti SA, čím sa vyhrotil spor medzi štátom a aerolíniami. O päť dní neskôr vláda zrušila určenie SA ako národného leteckého prepravcu.

Ako povedal vtedajší minister dopravy, pôšt a telekomunikácií SR Gabriel Palacka, spoločne s ministerkou financií SR Brigitou Schmögnerovou bol poverený navrhnúť spôsob zrušenia účasti štátu v spoločnosti SA s ohľadom na minimalizáciu dosahov na štátny rozpočet. Zároveň boli poverení navrhnúť spôsob, ako čo najefektívnejšie využiť tri lietadlá typu TU 154-M. Konštatoval, že projekt nesplnil svoj účel. SA napriek neodôvodneným zvýhodneniam oproti iným leteckým spoločnostiam dokázali zaviesť iba jedinú pravidelnú linku Bratislava-Moskva. Živili sa len takzvanými charterovými dovolenkovými letmi. Slovenský letecký trh potreboval podľa vtedajšieho ministra dopravy iný rozvoj.