Az új kormányfő a kabinetből Medgyessy által még meneszteni kívánt Gyurcsány Ferenc szocialista sportminiszter lett. Gyurcsány szeptember 29-én tette le az esküt a parlamentben, miután a koalíció egyhangúlag (197 vokssal) bizalmat szavazott neki. A 43 éves milliárdos vállalkozót, Medgyessy 2001-2003 közötti stratégiai főtanácsadóját az MSZP küldöttei augusztus 25-én nagy többséggel jelölték a miniszterelnöki posztra: 453:166 arányban győzte le a párt rendkívüli kongresszusán az elnökség által favorizált Kiss Péter kancelláriaminisztert. Az államügyektől még augusztus végén visszavonult Medgyessy helyett már szeptember elejétől (a kormányfő helyettesítésére feljogosított) Gyurcsány vezette a kabinetet a Hold utcai sportminisztériumból.

Az új kormányban hét új miniszter kapott helyet. Gyurcsány többnyire ott cserélt, ahol elődje is változtatni kívánt (az MSZP és az SZDSZ által birtokolt bársonyszékek aránya továbbra is 13:4 maradt). Csillag István gazdasági minisztert - akihez a szabaddemokraták korábban foggal-körömmel ragaszkodtak - Kóka János milliárdos vállalkozó váltotta fel, míg az Európai Bizottságba távozott Kovács László külügyminiszter utóda Somogyi Ferenc lett. A kormánystruktúrán is módosító Gyurcsány első intézkedései között megszüntette saját addigi tárcáját, viszont két tárca nélküli minisztert neveztetett ki Baráth Etele és Kolber István személyében az európai integrációs ügyek koordinálására, illetve a regionális fejlesztések irányítására. Igazságügyi, egészségügyi, illetve munkaügyi miniszterként október elején Petrétei József, Rácz Jenő és Csizmár Gábor debütált. A Medgyessy-adminisztrációnál fiatalabb, 48 év átlagéletkorú Gyurcsány-kabinettel az egykori állampárt rendszerváltó-reformista generációja után a hajdani KISZ-nómenklatúra reprezentánsai jutottak a csúcsra: az új kormányfőn és a régi-új kancelláriaminiszteren kívül további négy kormánytag is vezető pozíciót töltött be az 1980-as években (országos vagy helyi szinten) az ifjúkommunisták szövetségében.