Following independence, Gizenga served as Deputy Prime Minister (1960, 1961–62) as well as Prime Minister (1960–1961) and Head of State (1961) in rebellion. His government at Stanleyville was recognized by 21 African, Asian and Eastern European countries in February 1961. He was imprisoned from January 1962 to July 1964 and again from October 1964 to November 1965. He was exiled from 1965 to 1992.
Gizenga based his platform and political policies on those of Patrice Lumumba, Prime Minister at the time of independence for whom he served as Deputy Prime Minister and after Lumumba's murder as head of the rebel government. He was the presidential candidate of PALU in the July 2006 election. According to the provisional election results of 20 August, Gizenga came in third place with 13.06 percent of the vote, after Joseph Kabila and Jean-Pierre Bemba. On September 30, 2006, Gizenga signed a coalition agreement with the AMP, Kabila's platform, whereby he would back Kabila in the second round of the presidential election in October 2006, in exchange for the premiership. Kabila won the election and was sworn in as President on December 6, 2006. He subsequently appointed Gizenga as Informant, a position that involves identifying a parliamentary majority so that a government can be formed, and then appointed Gizenga as Prime Minister on December 30, 2006. Gizenga's new government, with 59 members (excluding himself), was appointed and announced on February 5, 2007. A new government under Gizenga was announced on November 25, 2007, with its size reduced to 44 ministers.
Gizenga delegated his duties as Secretary-General of PALU to Remy Mayele on September 14, 2007.
On September 25, 2008, Gizenga submitted his resignation as Prime Minister to Kabila. Later in the day he announced this on television, saying that he decided to resign due to his advanced age. According to Gizenga, he felt unable to continue in office: "For every man, even if you are sane and alert, your body has limits which you have to recognise". He had not received a response from Kabila at that point. Reacting to the news, the opposition Movement for the Liberation of Congo (MLC) said that Gizenga's "resignation constitutes an admission of failure and negligence from a government which, after nearly two years, left the country in a general state of crisis". The MLC disputed Gizenga's statement that his resignation was related to age and health. Kabila reportedly "officially acknowledged" Gizenga's resignation in a letter sent to Gizenga on September 28. The governing coalition, the Alliance for the Presidential Majority, remained in place after Gizenga's resignation, and negotiations were held regarding the selection of a successor to Gizenga.
His successor, Adolphe Muzito, was appointed by Kabila on 10 October 2008; Muzito is also a member of PALU and was Minister of the Budget in Gizenga's government. Gizenga promptly resumed his duties as Secretary-General of PALU on 13 October 2008, 13 months after delegating them to Remy Mayele.
On 30 June 2009, it was announced that Kabila had designated Gizenga as a National Hero, the DRC's highest honor. His admission to the Order of National Heroes made him its only living member and entitled him to a "monthly payment equivalent to the earnings of a prime minister, a residence, a garage with six vehicles, a guard including 12 members of the national police".