Algirdas Brazauskas, the leader of the Social Democratic Party of Lithuania had led the 12th government as the Prime Minister since 2001.

The outgoing government coalition "Working for Lithuania" finished second in the elections in October 2004, behind the populist Labour Party, but Brazauskas was again appointed the Prime Minister by President Valdas Adamkus on 29 November 2004.

The 13th cabinet received its mandate and started its work on 14 December 2004, after the Seimas gave assent to its program.

[5] The government collapsed in late spring of 2006, when in April New Union (Social Liberals) left the coalition and in May President Adamkus expressed no-confidence in Minister of Culture Vladimiras Prudnikovas and Minister of Health Žilvinas Padaiga, who were delegated by the Labour Party.

This criticism caused the Labour Party's council to withdraw its ministers from the government, prompting Brazauskas to resign on 1 June 2006.