Bajukovo ime se je v Sloveniji prvič resneje omenjalo po državnozborskih volitvah leta 1996. Tedaj so vse tri pomladne stranke podpisale dogovor o skupni povolilni koaliciji in tudi že sestavljale seznam kandidatov za ministrske položaje. Andrej Bajuk je bil eden njihovih glavnih adutov za finančnega ministra. Ker je Podobnik šel v povolilno koalicijo z Drnovškovo LDS, je projekt pomladne koalicijske vlade padel v vodo. Andreja Bajuka pa so kasneje omenjali kot avtorja zakonskega predloga Janševe stranke o privatizaciji bankah, ki v parlamentu ni dobil posebne podpore. Bajukovo ime se je začelo ponovno pojavljati lani ob pripravah na združitev SLS in SKD, še zlasti pa v začetku tega leta, ko sta Peterle in Janša ustanavljala Koalicijo Slovenija. Še pred podpisom koalicijskega sporazuma konec januarja je Bajuk veljal za enega ključnih ljudi v novi koaliciji in po ustanovitvi koalicije je prevzel vodenje njenega strokovnega sveta. Pri tem je zanimivo, da je Bajuk veljal bolj za Janševega človeka kot za Peterletovega ali Podobnikovega, vendar je na koncu pred dobrima dvema tednoma vstopil v Peterletovo stranko in kot član SKD tudi kandidiral za podpredsednika združene stranke.