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 Ran 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.
Ben-Eliezer warned in 2012: "So far Palestinians have kept quiet, but one day they will awake and the explosion will happen. People don't accept [being] under military rule for 50 years."