Early political career
Upon the founding of the Alliance for Democracy in Mali (ADEMA-PASJ), Keïta became its secretary for African and international relations at its constitutive congress, held on 25–26 May 1991. He was the deputy director of ADEMA candidate Alpha Oumar Konaré's successful presidential campaign in 1992. The new president named Keïta as his senior diplomatic adviser and spokesman in June 1992, and then in November 1992 Konaré appointed Keïta as Ambassador to Côte d'Ivoire, based in Abidjan and with non-resident accreditation in Gabon, Burkina Faso and Niger.
In November 1993, Keïta was appointed to the Malian government as minister of external affairs, Malians abroad, and African integration. On 4 February 1994, President Konaré named him prime minister, a position he held until February 2000. At ADEMA's first ordinary congress, held in September 1994, Keïta was elected as the president of ADEMA. Following presidential and parliamentary elections held in 1997, he resigned from his post as prime minister on 13 September 1997 and was promptly reappointed by Konaré, with a new government appointed on 16 September. Keïta was re-elected as ADEMA president in October 1999, and in November 1999, he was named vice-president of the Socialist International.
Disagreements within ADEMA forced him to resign as prime minister on 14 February 2000, and then from the leadership of the party in October 2000. He then founded his own party, the Rally for Mali (RPM), which he has led since its creation was announced on 30 June 2001. He stood as a candidate in the 2002 presidential election, receiving the strong backing of many Muslim leaders and associations. Despite this support, some people doubted that Keïta's policies were particularly compatible with Islam, pointing to the creation of casinos and lotteries while he was prime minister. In the first round of the election, held on 28 April, he received about 21% of the vote and took third place, behind Amadou Toumani Touré and Soumaïla Cissé. He denounced the election as fraudulent, alleging that he was deliberately and falsely excluded from the second round, and along with other candidates sought the invalidation of results. On 9 May the Constitutional Court ruled that the second round should proceed with Touré and Cissé as the top two candidates, despite acknowledging significant irregularities and disqualifying a quarter of the votes because of the irregularities. According to the Constitutional Court, Keïta won 21.03% of the vote, only about 4,000 votes less than Cissé. On the same day, Keïta announced the support of his Espoir 2002 alliance for Touré in the second round; regarding the Court's ruling, he described himself as "a law-abiding person" and said that the Court had followed the law. The second round was won by Touré.
In the July 2002 parliamentary election, Keïta was elected to a seat in the National Assembly from Commune IV in Bamako District in the first round. He was then elected as President of the National Assembly on 16 September 2002, receiving broad support, including the backing of ADEMA. He received 115 votes from the 138 participating deputies; the only other candidate, Noumoutié Sogoba of African Solidarity for Democracy and Independence (SADI), received eight votes, while 15 deputies abstained.
Keïta was also elected as President of the Executive Committee of the African Parliamentary Union on 24 October 2002 at its Khartoum Conference.
He ran for president again, as the candidate of the Rally for Mali, in the April 2007 election, having been designated as the party's candidate on 28 January 2007. Touré won the election by a landslide, while Keita took second place and 19.15% of the vote. As part of the Front for Democracy and the Republic (FDR), a coalition that included Keita as well as three other presidential candidates, Keita disputed the results and sought the annulment of the election, alleging fraud. On 19 May, he said that the FDR would abide by the decision of the Constitutional Court to confirm Touré's victory.
In the July 2007 parliamentary election, Keïta ran for re-election to the National Assembly from Commune IV in Bamako, where 17 lists competed for the two available seats, on an RPM list together with Abdramane Sylla. Keïta's list received 31.52% of the vote in the first round, held on 1 July, slightly ahead of the list of independent candidate Moussa Mara, which received 30.70%. In the second round on 22 July, Keïta's list narrowly prevailed, winning 51.59% of the vote according to provisional results. He was not a candidate for re-election as President of the National Assembly at the opening of the new National Assembly on 3 September; the position was won by ADEMA President Dioncounda Traoré.
Keïta was a member of the Pan-African Parliament from Mali. As of 2007–2008, he was a member of the Commission of Foreign Affairs, Malians Living Abroad, and African Integration in the National Assembly. In addition to serving in the National Assembly, Keïta was a member of the Parliament of the Economic Community of West African States.