Re-elected again in 2003, Ben-Eliezer served as Minister of National Infrastructure from 10 January 2005 until 23 November, when Labor left the government. In the Labor Party leadership election on 9 November 2005, he came third with 16.8% of the vote, behind Amir Peretz and Shimon Peres. He retained his seat again in the 2006 elections, and was appointed Minister of National Infrastructure in Ehud Olmert's government.
In March 2007, Ben-Eliezer was forced to cancel a trip to Egypt after being warned by Egyptian intelligence that he could be arrested, when Egyptian media and opposition implicated him in the 'massacre' of 250 Egyptian POWs during the Six-Day War following an Israeli documentary. However, the allegations are disputed by both Binyamin Ben-Eliezer and the documentary film-maker Ron Edelist. Placed eighth on the party's list, he was re-elected again in the 2009 elections and appointed Minister of Industry, Trade and Labour. He resigned from the cabinet after Ehud Barak left the Labor Party to establish Independence in January 2011.
Ben-Eliezer is considered a hawk on foreign policy and was one of the main architects of the invasion of Lebanon as well as a strong proponent for Operation Defensive Shield. He advocated halting peace talks with Palestinians until there was an end to violence against Israelis, although he believed once their leadership is able to put a stop to "terrorism" and abandon it as a political tool there should be "compromise" in final status talks with the Palestinian Authority.
He lives in Rishon LeZion and is married with five children. Some of his granddaughters live in the United States of America. He is fluent in Hebrew, Arabic and English.