„A nyolcvanas években nem volt divat angolt tanulni, de ő már a harmadikban nyelvvizsgázott. Ez a mentalitás egyébként a fociban is megnyilvánult: nem volt tehetséges kapus, de ütötte-vágta magát az eredményekért" - mondta az egykori iskolatárs. Ezt a céltudatosságot szerinte Bajnai a családjából hozta. Édesapja az ország egyik legsikeresebb vállalatát, a Bajai Lakberendező, Építő és Vasipari Szövetkezetet igazgatta, amelyet sokan csak „Bajnailévisz"-nek hívtak. A keresztnevét a Gordon's Dry Gin vagy Gordon Banks egykori híres angol kapus után öröklő fiatalember (a családi emlékezet nem egyértelmű) már a gimnáziumban diákvezető volt, a Marx Károly Közgazdaságtudományi Egyetemen pedig ő lett az ország első hallgatói önkormányzatának elnöke. Nevéhez fűződik például az országos visszhangot kiváltó egyetemi menzasztrájk megszervezése 1987-ben.
Bajnai egyetemista barátaival részt vett a Közgazdászhallgatók Nemzetközi Szervezete (AIESEC) magyar részlegének a működtetésében. „Akkoriban szűnt meg a KISZ, egy vákuum keletkezett az ifjúsági területen, amibe legügyesebben a Fidesz tudott benyomulni, a KISZ szenvedett, de az AIESEC lehetőséget teremtett a közgazdászoknak utazni, kapcsolatokat építeni, nem annyira politikai, hanem inkább egy karrier-építő szervezet volt" - magyarázta a Heteknek a miniszterelnök-jelölt egy akkori ismerőse, aki szerint Bajnai és baráti köre családi indíttatásból „csont balosak" voltak.
Az AIESEC tagja volt az 1988-ban Pozsgay Imre akkori államminiszter bábáskodásával megalakult Magyarországi Ifjúsági Szervezetek Országos Tanácsának (MISZOT). A szervezet elnökévé Stumpf Istvánt választották, aki ezzel kapcsolatban lapunknak korábban úgy nyilatkozott: „A Fidesz számára én jelentettem a garanciát, hogy nem egy olyan szervezet, amelynek az a célja, hogy őket bedarálják." (Hetek, 2003. november 28. Egy generáció útja a hatalomba)