Yusuf Kalla, who stood as Yudhoyono's running mate in September presidential polls, was chosen to lead Golkar, the former political vehicle of former president Suharto, after he beat incumbent Akbar Tanjung.
The victory during a chaotic party conference at Nusa Dua on the resort island of Bali marks a major coup for the president, who has faced an uphill struggle to push reforms through a parliament dominated by a hostile Golkar.
Tanjung, who scored 156 votes to Kalla's 323, had pledged to strengthen the party's resolve as an opposition force if he was elected for another five years. Instead the vice president is likely to steer Golkar behind Yudhoyono.
A number of Indonesia's political hierarchies shook when Yudhoyono was elected. A struggle continues for control of the two largest Muslim organisations between the president's allies his opponents' allies. The importance of the Golkar leadership is shown by the attempt to poison Yusuf Kalla before the Golkar convention.
Winning control of Golkar gives Yudhoyono a legislative majority and is a massive step toward making his official power real.