Toledo first ran for president in 1995, against Alberto Fujimori, He won 4% of the vote to Fujimori's 64%. He again challenged Fujimori in 2000, forcing him into a second round before pulling out of the race, alleging election fraud.
Toledo wanted the vote to be postponed while new vote-counting software was inspected but the government refused. After Fujimori was forced out of office in November 2000, elections were set for 8 April 2001 by the interim president Paniagua. The campaign for the 2001 election was a fight between three candidates: the front-runner Toledo, former president and leftist politician Alan Garcia, and a religious and right-leaning Lima lawyer trying to become Peru's first female president, Lourdes Flores Nano. The campaign was punctuated by personal attacks, racial insults, and some violence. Information was revealed that Toledo had tested positive for cocaine in October 1998; Toledo claimed he was abducted by Fujimori intelligence agents and was drugged against his will in an attempt to blackmail him.
In the first round of elections, Toledo (of the "Peru Possible" party) won 36% of the vote to Garcia's 26% and Flores's 24%, forcing a run-off between Toledo and Garcia. Garcia, who had become the youngest president in Peru's history in 1985, used the 70-year-old political structure of his party, the American Popular Revolutionary Alliance, to stage colorful well-planned rallies that energized the left. Toledo capitalized on being an Amerindian as well as being a moderate who would "build a modern nation, but one that celebrates its ancient heritage and roots." In the run-off election held 3 June, Toledo won 53.1% of the vote compared to Garcia's 46.9%. An estimated 12.5% of voters cast blank or void ballots. Alejandro Toledo became Peru's first elected president of Indian descent.
To promote unity, Toledo pledged to work with Garcia in rebuilding institutions—particularly the judiciary and military—damaged by Fujimori's last, corrupt years in office. Toledo was inaugurated on 28 July 2001 in the Peruvian Congress but he held a "second inaugural" at the Incan ruins of Machu Pichu.