Ve všeobecných volbách v březnu 2004 – prvních od doby, kdy Mahathir po 22 letech u moci odstoupil – umírnění muslimové pomohli Abdalláhu Badávímu k drtivému vítězství. Propuštění Anwara Ibrahíma krátce nato ještě dále posílilo prestiž nového premiéra jako vůdce, jenž by mohl překlenout vnitřní spory mezi Malajsijci i mezi muslimy.
2004年3月举行的大选之中¾也是执政22年的马哈蒂尔辞职后的首次选举¾温和派的穆斯林帮助阿卜杜拉.巴达维赢得了压倒性的胜利。不久后安瓦尔·伊伯拉罕的释放令新总理声名雀起，人们把他看作能够修复马来人和穆斯林内部冲突的杰出领袖。