V lete, 30. júla 1999, sa predstavitelia MDPT dohodli so zástupcami SA na vyriešení všetkých sporných otázok mimosúdnou cestou a podpísali Generálnu dohodu. Na základe tejto dohody sa štát ujal v spoločnosti SA svojich akcionárskych práv a spoločnosti pridelil licenciu leteckého prevádzkovateľa. Na jej základe začali SA dňom 9. augusta opäť s pravidelnou leteckou prevádzkou lietadlom Saab 340, ktoré mala spoločnosť prenajaté, a lietadlami TU 154-M. Znovuotvorenie pravidelnej leteckej linky Bratislava - Moskva nastalo 9. novembra 1999. Spoločnosť tiež prvýkrát 22. novembra 1999 otvorila pravidelnú leteckú linku Bratislava - Mníchov, ktorú dočasne uzatvorila 1. októbra 2000 a v súčasnosti ju už neprevádzkuje.

K ďalším zmenám v spoločnosti došlo 12. júla 2001. Mimoriadne valné zhromaždenie SA zobralo na vedomie abdikáciu Viliama Vetešku z postu predsedu dozornej rady a za nového predsedu dozornej rady zvolilo Milana Čiča. Na voľné miesto člena dozornej rady MVZ zvolilo Rudolfa Janáča. Krátko na to, 31. júla 2001 sa vtedajší generálny riaditeľ SA Pavol Mladý rozhodol ukončiť svoje pôsobenie v tejto funkcii, ktorú zastával od 1. júla 1998. Novým generálnym riaditeľom spoločnosti sa 1. januára 2002 stal Ing Miloslav Mészáros.

Vláda SR sa 7. novembra 2001 rozhodla o zvýšení podielu štátu v spoločnosti SA z vtedajších 34 % na 82,4 %, čím chcela odvrátiť možnosť ich konkurzu a pripraviť spoločnosť na privatizáciu. Rozhodla, že sa tak stane formou vkladu troch lietadiel TU 154-M v trhovej hodnote 130 až 250 miliónov Sk, ktoré mala firma v prenájme od štátu.

Plánovaný vklad štátu do spoločnosti SA formou 3 lietadiel TU 154-M nakoniec dosiahol asi 600 miliónov Sk. Na túto hodnotu totiž 3 štátne lietadlá ocenil v januári 2001 nezávislý expert. Zvýšenie základného imania z vtedajších 221,21 milióna Sk na 857,71 milióna Sk a navýšenie štátneho podielu na 90,5 % odsúhlasilo 8. marca 2002 jednomyseľne mimoriadne valné zhromaždenie spoločnosti. MDPT SR ako zástupca štátu v spoločnosti SA, upísalo nové akcie tohto leteckého dopravcu v objeme 737 miliónov Sk.

V súlade s plánom rozvoja spoločnosti doviezli SA 23. júna 2002 na lízing nový Boeing 737-300 s kapacitou 148 miest.

Ďalšie mimoriadne valné zhromaždenie SA 5. decembra 2002 iniciovalo zmeny v dozornom orgáne spoločnosti v prospech budúceho 91-% akcionára - štátu. Nakoniec vláda SR 8. decembra 2002 schválila vklad troch štátnych lietadiel TU 154-M a leteckých sedadiel v hodnote 642,016 milióna Sk do majetku spoločnosti SA. Podiel MDPT v SA tak stúpol z 34 na 89,49 %.

V roku 2003 sa 12. marca stal novým generálnym riaditeľom spoločnosti predseda predstavenstva Tomáš Slivka. O tri mesiace neskôr, 6. júna 2003 SA podpísali s lotyšskou leteckou spoločnosťou RAF-Avia Airlines obchodnú zmluvu o spolupráci v oblasti leteckej prepravy a onedlho podpísali zmluvu s lotyšskou leteckou spoločnosťou RAF - Avia Airlines o zriadení leteckej linky medzi Bratislavou a Rigou. V máji 2003 došlo k otvoreniu pravidelného leteckého spojenia Bratislava - Kyjev - Charkov v spolupráci s ukrajinskou spoločnosťou Aeromost Kharkov.

SA otvorili 27. októbra 2003 novú pravidelnú linku Bratislava Brusel, Brusel - Bratislava, ktorú neskôr v rámci spolupráce pomáhali prevádzkovať rakúske aerolínie - Austrian Airlines (AUA).

Aj ďalšiu pomoc SA poskytla 29. septembra 2004 spoločnosť AUA, ktorá sa zaručila za ich pôžičku 5 miliónov EUR od Erste Bank. Vďaka tomu AUA obsadila v SA niekoľko manažérskych postov vrátane dvoch miest v predstavenstve. Na valnom zhromaždení SA (4. novembra 2004) dosadilo potom MDPT do predstavenstva a dozornej rady podniku zástupcov rakúskeho dopravcu. Novou predsedníčkou päťčlenného predstavenstva sa stala Christiana Böhmová Mayerová.

Hlavným problémom SA bola od začiatku ich existencie podľa MDPT podkapitalizácia, nakoľko základné imanie sa navyšovalo len nepeňažnými vkladmi. Takýmto spôsobom aerolínie nezískali zdroje potrebné na rozvoj nových projektov, ale dochádzalo len k čiastočnému znižovaniu vzniknutých záväzkov. Negatívne na hospodárenie SA vplývali aj tri lietadlá TU 154-M, ktorých prevádzkové náklady boli vysoké a navyše boli tieto stroje kapacitne nevhodné pre rozbeh pravidelnej dopravy. Spoločnosť sa preto v roku 2002 rozhodla ich predať. Posledné lietadlo TU 154-M naposledy vzlietlo z bratislavského Letiska M. R. Štefánika 19. novembra 2003. Zníženie cien charterových letov v dôsledku konkurenčného boja znamenalo pre SA prehĺbenie dlhov.

Minister dopravy Pavol Prokopovič už minulý rok nevylúčil kapitalizáciu pohľadávky AUA voči SA, čo de facto znamenalo vstup AUA do SA.

O zvyšný asi 10-% balík akcií SA sa v závere roka 2004 stále delili spoločnosti Devín Group, s. r. o., Turčianske Teplice, Wili Travel, s. r. o., Púchov a ruská korporácia JAK. V prvých troch kvartáloch roka 2004 spoločnosť prepravila 160 000 pasažierov, čo v porovnaní s rovnakým obdobím roka 2003 predstavovalo pokles v počte pasažierov o 40 000.