Mitchell's entry into politics was facilitated by Grenada's post-revolutionary return to democratic rule in 1983. Like many others, Mitchell returned to his home country from the United States to join in Grenada's democratic rebirth. He became a member of the New National Party (NNP), a coalition of center-right parties at the core of which was the old opposition party, the GNP. The NNP coalition, promoted by several Eastern Caribbean leaders, and indirectly by the United States, was successful in gaining power. Mitchell was put in charge of the Ministries of Works, Communications, Public Utilities, Civil Aviation, and Energy. His base of support was in the black working classes.
By 1987, the NNP coalition had collapsed as a result of internal differences over leadership style and policy. The most important coalition partners left to form the National Democratic Congress (NDC, formerly National Democratic Party). Mitchell used the opportunity to express his own dissatisfaction with the aging and authoritarian leadership of Herbert Blaize, who had been the GNP leader and was given the leadership of the NNP coalition. Beyond personal ambition and personality differences, Mitchell opposed the government's fiscal policy, restrictions on militant groups, and failure to alleviate youth unemployment.
In 1989, Mitchell mounted a challenge to Blaize's leadership and succeeded in being elected to head the NNP. This created an unusual situation. Blaize was no longer the leader of the majority party in Parliament but still continued to rule as prime minister. In July 1989, Blaize dismissed Mitchell from the cabinet and moved to form his own party, The National Party (TNP). Mitchell, deprived of a majority in Parliament, was unable to carry through with a proposed noconfidence vote intended to oust Blaize from the prime ministership. Blaize remained as prime minister until his death in December 1989.
Mitchell entered the 1990 elections plagued by broad allegations of corruption (which were never proven although a commission of inquiry was set up), and by some popular dissatisfaction over his aggressive removal of Blaize from party leadership. At the same time, the NNP/TNP administration had not demonstrated an ability to solve the country's economic problems. Thus it was not surprising that the election was won by the NDC, which formed the government in coalition with the TNP. Mitchell's party won only two seats and formed the opposition, along with Eric Gairy's GULP.
The NDC proved to be no better that the NNP at improving the economy. In particular, despite overall statistical growth in the economy, unemployment rose considerably; foreign investment did not bring major expected rewards; tourism declined; and the agricultural sector suffered various setbacks. In 1995, Mitchell harnessed the discontent not only of the working class but also the heavily taxed middle classes. While he promised a repeal of the national income tax and jobs and other programs for the large number of unemployed young people, Mitchell was careful not to make any excessive promises. His success was attributed to his appeal to moderation and to national unity at a time of national and regional economic uncertainty.
In the period before the 1998 election, Mitchell's government was accused by the opposition of a lack of accountability and transparency, and of having an excessive focus on expensive large projects that did little to lower the high unemployment rate. Mitchell was successful in countering these accusations by emphasizing that rumors of corruption were completely unsubstantiated and by outlining the benefits that his government's projects had brought to the people of Grenada. Beyond these policy issues, Mitchell's overwhelming success was premised on the promise of continuing domestic stability and investor confidence. Mitchell also benefited from accusations against Raphael Fletcher of improper use of travel monies while in government and similar accusations of impropriety against the daughter of former prime minister, Eric Gairy. Finally, Mitchell's success was attributable to widespread respect for his leadership and willingness to allow him more time to complete his promising public policy agenda.
The NNP, which held a slim eight–seven majority in Parliament in 1998, lost its majority when two of Mitchell's supporters crossed over to the opposition. Mitchell was forced to call early elections (18 months ahead of schedule) for January 1999. Turnout was low, with only 56.4% of registered voters casting ballots. Opponents complained they only had six weeks to campaign, which gave Mitchell an advantage. His NNP captured all 15 seats in the January elections despite accusations of corruption in his government. Mitchell was accused of irregularities in awarding public works contracts and negotiating with foreign investors with questionable credentials. Mitchell has been credited with stimulating the economy and attracting investment. The Organization of American States (OAS), which monitored the elections and called them fair, later said Grenada should consider campaign finance reform, as opponents claimed they could not compete against the better-funded NNP. With their January 1999 victory, Mitchell's ruling NNP became the first in Grenada to win two successive terms since 1984 when parliamentary democracy was restored in the nation.