Although he did not win a seat in the 1999 elections, Herzog served as government secretary in Ehud Barak's cabinet until 2001 when Barak was defeated by Ariel Sharon in a special election for Prime Minister. In 1999, he was also investigated in the 'Amutot Barak' scandal (a scandal involving allegations that the party funding law was violated), but maintained his silence, similar to the American "taking the 5th Amendment". The Attorney General, therefore, decided to close the case against him due to lack of evidence. From 2000 until 2003, he served as chairman of the Israel Anti-Drug Authority.
Herzog won a seat in the 2003 election as a member of the Labor Party, and was appointed Minister of Housing and Building at his request when Labor joined Ariel Sharon's coalition government on 10 January 2005. However, on 23 November 2005, he resigned from his cabinet post along with the rest of the party.
Prior to the 2006 elections, Herzog won second place on Labor's list in the party's primaries. He was initially appointed Minister of Tourism in Ehud Olmert's Kadima-led coalition, but was reassigned to the Social Affairs ministry in March 2007 after Yisrael Beiteinu was awarded the Tourism Ministry following their late entry to the governing coalition, and was also appointed Minister of the Diaspora, Society and the Fight Against Antisemitism. He was again second on the party's list for the 2009 elections. Following the election, he was appointed Minister of Welfare & Social Services and Minister of the Diaspora, Society, and the Fight Against Antisemitism. However, he resigned from the cabinet after Ehud Barak left the Labor Party to establish Independence in January 2011.
Herzog is chairman and whip of the Israeli-Australian Parliamentary Association. He is also one of the few Knesset members who still serves in the military reserve (with the rank of Major).
In 2011 Herzog was an unsuccessful candidate for the Labor Party leadership. He finished third in the primaries that year, after Shelly Yechimovich and Amir Peretz.
Herzog has reportedly reached out to Shas leader Aryeh Deri to increase cooperation between the two opposition factions.
In June 2014, Herzog criticized PM Benjamin Netanyahu for failing to engage the international community, failing to present a proposal for peace with Palestinians, and failure to work effectively with the President of the United States, Barack Obama. Herzog declared that Netanyahu's "loathing and hostility for Barack Obama” was one of his greatest failures, since it put Israel's security at risk.
With the governing coalition dissolving and new elections expected in March 2015, Herzog called on Hatnua and Kadima parties to join his Labor Party in forming a new coalition. In an interview with YNET, he stated, "I am capable of replacing Netanyahu. I will do everything in order to establish a bloc before the elections.” Shortly thereafter, Herzog and Tzipi Livni, who was justice minister and is head of a centrist faction, announced they would campaign on a joint slate in the upcoming election in an effort to keep Netanyahu, leader of the Likud Party, from securing a fourth term as prime minister. The joint list is named Zionist Union.