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. 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 managed to win 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).