Medgyessy began his political career at the Ministry of Finance, where he held various positions between 1966 and 1986, including head of the State Budget Department, and, in 1982, Deputy Minister of Finance. He was appointed Minister of Finance in 1987, and is credited with reforming the Hungarian banking sector and introducing a new "European-style" tax system, which helped facilitate Hungary's transition to a market economy. From 1988–90, Medgyessy was Deputy Prime Minister in charge of Economic Affairs in the reform government which was implementing political change, and was given the task of economic liberalization and the preparation of corporate law that would lay the foundations for privatization. He served once again as Minister of Finance from 1996–98 in the government of Gyula Horn, distinguishing himself by curbing inflation and undertaking public sector finance reform. Under his leadership, the Finance Ministry submitted to Parliament a European-style pension reform bill.
Although not a member of the Hungarian Socialist Party, in June 2001 the party nominated him as their candidate for prime minister. After the Socialists won the elections in April 2002, Parliament elected Medgyessy prime minister to head a coalition with the Alliance of Free Democrats (Liberals).