Kodjo was born in Tokpli, located in Yoto Prefecture, in 1954; his parents were Dossou Kodjo and Kédjé Flora Dosseh. He studied in France and received a degree in organizational management from the University of Poitiers in January 1983.
Back in Togo, Kodjo was Commercial Director of SONACOM from 1985 to 1988 before President Gnassingbé Eyadéma appointed him to the government as Minister of Youth, Sports, and Culture on 19 December 1988. He remained in that post until September 1991, when a transitional government led by Prime Minister Joseph Kokou Koffigoh took office. He was appointed as Minister of Territorial Administration and Security in September 1992, but Koffigoh dismissed him, along with another member of the Rally of the Togolese People (RPT), Minister of Communications and Culture Benjamin Agbéka, on 9 November 1992. Kodjo and Agbéka, with Eyadéma's support, refused to leave the government, despite protests and Koffigoh's intent to take the matter to the Supreme Court; Kodjo remained in his position until February 1993, when he became Director-General of the Autonomous Port of Lomé.
Kodjo served for more than six years as Director-General of the Autonomous Port of Lomé. In the March 1999 parliamentary election, he was elected to the National Assembly as the RPT candidate in the Third Constituency of Yoto Prefecture; he was the only candidate and received 100% of the vote. Following the election, he was elected as President of the National Assembly in June 1999. After a little over a year in that position, President Eyadéma appointed Kodjo as Prime Minister on 29 August 2000, replacing Eugene Koffi Adoboli after Adoboli was defeated in a no-confidence vote.
Kodjo said on 30 August 2001 that the Constitution should be changed to enable Eyadéma to run for a third term in 2003. Although Kodjo was widely speculated to be Eyadéma's intended successor after he became Prime Minister, he and Eyadéma came into conflict, and he was dismissed as Prime Minister by Eyadéma on 27 June 2002, reportedly due to differences within the RPT. In an article published in Le Scorpion newspaper on 28 June, he criticized Eyadéma. He promptly left Togo, and in early July 2002 he was declared wanted by a court for allegedly dishonoring the President and disrupting public order. On 6 August 2002, the RPT Central Committee voted unanimously to expel Kodjo from the party, along with former National Assembly President Dahuku Péré, for high treason; he was also expelled from the prestigious Order of Mono on 18 July.
After leaving Togo, Kodjo lived in exile in France, and from there he continued his criticisms of Eyadéma. The Togolese government issued an international arrest warrant for Kodjo in mid-September 2002, accusing him of corruption and saying that he had fled Togo to avoid prosecution for it. The government also complained about Radio France Internationale's broadcasting of an interview with Kodjo in September, which RFI had done despite government pressure. He denounced the amendment to eliminate presidential term limits, saying that it was Fambaré Ouattara Natchaba who initially made that proposal publicly and that he had supported the proposal at the time for internal reasons of the RPT.
Following the disputed June 2003 presidential election, Kodjo said in an interview with the newspaper Motion d'information that, contrary to the official results, Eyadéma had actually lost the election. Accusing Eyadéma of remaining in power through violence, Kodjo said that Eyadéma should admit defeat and leave politics in order to resolve the country's political troubles and prevent war.
He returned to Togo on 8 April 2005, following Eyadéma's death, but was promptly imprisoned for alleged misappropriation of funds while serving as Director-General of the Autonomous Port of Lomé. In September 2005 he formed a new party, the Democratic Alliance for the Fatherland (known simply as the Alliance), together with Dahuku Péré.
He later ran for election to the position of President of the Togo Football Federation, but at its extraordinary congress on 9 January 2007 he placed second behind Avlessi Adaglo Tata, receiving 14 votes from delegates against 24 for Tata; he placed ahead of Eyadéma's son Rock Gnassingbé, who was the Federation's incumbent president and received eight votes.
Kodjo announced in early August 2008 that he would stand as the candidate of a new party, the Organisation pour bâtir dans l'union un Togo solidaire (OBUTS), in the 2010 presidential election. He formally submitted his candidacy on 14 January 2010. Although the deadline for the submission of candidacies was 15 January, Kodjo was the first person to formally submit his candidacy. Upon learning that he was first, Kodjo declared that it was "a very good sign" and that he would also be "the first" to be declared the winner of the election.