Olusegun Obasanjo, President of Nigeria from 1999 to 2007 is a possible candidate.
He was imprisoned in June 1995 on charges of being involved in plotting a coup and was released in June 1998. Although a general, he then ran as a civilian for president in February 1999 and won the election with almost 63% of the vote as the candidate of the People's Democratic Party.
Obasanjo was convicted based on evidence obtained through torture and was widely perceived to be a political prisoner as he had criticized the Sani Abacha regime of human rights abuses. His sentence was reduced from life to 15 years "after pressure from friends abroad, including South Africa's Nelson Mandela, former US President Jimmy Carter and former German Chancellor Helmut Schmidt." The imprisonment of Obasanjo and others by the regime of Sani Abacha was condemned internationally. When Sani Abacha died on the 8th of June 1998, his successor Abdulsalami Abubakar ordered that Obasanjo and eight other political prisoners be released. Obasanjo was freed about a week after Abacha's death and elections were held in February 1999, overseen by the Independent National Electoral Commission.
Obasanjo has the distinction of being Head of State both before and after being imprisoned. His first stint was from 1976 to 1979 as a military ruler following the assassination of General Murtala Mohammed. He voluntarily left office in 1979, handing over to the democratically elected Shehu Shagari. This, combined with his military contacts and the fact that he was widely perceived to have been imprisoned for political reasons, meant that the electoral commission had no problem with a former prisoner running in the election.
When Obasanjo was last in office he gained international respect
through his efforts to end white minority rule in South Africa and
Zimbabwe, supporting neighbouring states such as Angola and
Mozambique. After relinquishing power, Obasanjo retired to his second
home at Otta, outside Abeokuta, where he enjoyed his image as a man of
Obasanjo's argument that his own military background makes him
uniquely qualified to keep the Army under control has carried more
weight among the electorate than fears that he will not be his own
man. He also won widespread credibility when he voluntarily handed
over power to a civilian government in 1979.
Source: Obasanjo Biography (University of Pennsylvania, African Studies Center)
Although there were some reported irregularities and the result of the election was contested by Obasanjo's rival, former finance minister Olu Falae, the Nigerian courts rejected requests to have the result annulled. Obasanjo was elected for a 2nd term in 2003.
You may also want to consider Éamon de Valera who escaped from prison in February 1919 and became President of Dáil Éireann in April 1919 (2nd Minsitry) under it's unilateral declaration of independence. However, the Irish Republic of 1919-22 was not recognized by the major powers of the time.
De Valera had been elected Sinn Fein MP for East Clare in July 1917 after being released in June 1917 (he had been imprisoned in 1916 following the Easter Rising). He was rearrested in May 1918 and then escaped from Lincoln jail in February 1919. During his imprisonment, he was also elected for a second constituency in the December 1918 General Election. Unsurprisingly, as far as most Irish voters were concerned, his prison record was no handicap.