W latach 2006–2007 Gordon Bajnai pełnił funkcję komisarza rządowego w Narodowej Agencji Rozwoju. Od 1 lipca 2007 do 30 kwietnia 2008 był ministrem rozwoju regionalnego i samorządu lokalnego w gabinecie premiera Ferenca Gyurcsánya. 16 maja 2008 został mianowany na urząd ministra gospodarki i rozwoju narodowego w jego rządzie.
Premier thumb|240px|Gordon Bajnai wraz z Cippi Liwni (Jerozolima, 2009) 29 marca 2009, po wcześniejszej rezygnacji ze stanowiska premiera i przewodniczącego socjalistów złożonej przez Ferenca Gyurcsánya, Gordon Bajnai został kandydatem Węgierskiej Partii Socjalistycznej na stanowisko premiera Węgier. Następnego dnia jego kandydaturę zaakceptował również Związek Wolnych Demokratów. Gordon Bajnai zapowiedział konieczność przeprowadzenia w kraju szybkich reform w celu przezwyciężenia kryzysu gospodarczego. 5 kwietnia został oficjalnie nominowany na stanowisko premiera Węgier w czasie kongresu MSZP. Jego kandydaturę poparło wówczas 93% delegatów.