Az ÁPV Rt. először 2004. szeptember 7-én tette közzé a Malév 99,95 százaléknyi részvényének eladását szolgáló nyilvános, egyfordulós privatizációs pályázati felhívását. Az első pályázat beadási határideje 2004. október 20-a volt, amelyre ajánlatot mindössze egy pályázó, az Aviation Solution International (ASI) konzorcium nyújtott be. Az ASI igen alacsony, 150 milliós ajánlatát – mely szerint a Malév 36 milliárdos hitelállományát sem vette volna át – a privatizációs szervezet igazgatósága úgy ítélte meg, hogy a pályázó nem tett eleget a pályázati kiírásnak, ezért a tendert eredménytelennek nyilvánította.
Némi változtatás után az APV Rt. 2004 december végén ismét meghirdette a Malév 99,95 százalékos reszvénycsomagjának eladását. A befektetőknek itt is a teljes állami részvénycsomagra kellett ajánlatot tenniük, de a második kiírás értelmében a tulajdonba lépés legfeljebb egy éven belül, több lépcsőben is megtörténhet.
A második tenderbontás február végén volt, ahol az APV Rt. öt pályázat közül hármat ajánlatnak, kettőt pedig széndéknyilatkozatnak minősített.
Bár az APV Rt. a verseny és a tranzakció sikere érdekében a pályázók kilétéről és az ajánlatok tartalmáról az eredményhirdetésig akkor nem adott tájékoztatást. De valószínűsíthető volt, hogy a korábbi ajánlattevő, az ASI konzorcium ugyanezen a néven, de összetételét megváltoztatva ismét ringbe szállt. Továbbá feltehető volt, hogy ebben a fordulóban a pilóták Sky Alliance nevű cége valamint krasznojarszki, kirgiz és olasz cégek is érdekődést mutattak a magyar légitársaság iránt.
Időközben a második fordulót is érvénytelennek nyilvánították és az ÁPV Rt. közvetlenül próbált egyezkedni a jelöltekkel. A előző sikertelen pályázati fordulóval ellentétben a pontozás itt már a két kulcskérdésre (adósságrendezés, tőkeemelés) adott befektetői válaszra összpontosított. Sajtóértesülések szerint azonban a befektetőjelöltek az előző két sikertelen pályázaton nem mutattak hajlandóságot arra, hogy átvállalják a Malév mintegy harmincmilliárd forintnyi adósságának egészét, ráadásul korábban jelezték: nem vállalnak garanciát arra, hogy minden mostani alkalmazottat megtartanak.
Újabb kiírás következett. A megjelölt július 5-ei határidővel ezúttal hárman adták be a jelentkezésüket, amelyből kettő, az orosz Airbridge, amelynek tagja a KrasAir is és az Aviation Solution konzorcium hivatalosan is jelezte a sajtó felé az érdeklődés. A harmadik pályázó kilétéről eddig azonban csak talalgatások voltak: egyes lapértesülések az Argus Capital Ltd.-t, vagy a milánói Air Europe-ot vélték harmadik szereplőnek.
E hármasból sajtóértesülések szerint a KrasAir irányította konzorcium ajánlotta a legtöbbet, és mivel bizonyos feltétekekkel a 36 milliárd forintra rúgó hitelállomány felét is hajlandó volt átvállalni, valószínúsíthetó volt, hogy a privtizációs pályázat győztesének is az AirBridge-et lehet kikiáltani.
