2004 nomination contest

In 2004, the decennial redistribution process took place and Valeri's old riding of Stoney Creek, which straddled the border between Hamilton and Grimsby, was split in two. A part of Valeri's Stoney Creek riding was merged with a part of Hamilton - East. A slight majority of the constituents of the new riding of Hamilton East - Stoney Creek were from Valeri's former riding. Although the other Hamilton-area Members of Parliament shifted to the eastward half of their ridings, in Valeri's case this would have meant shifting from a suburban Hamilton riding to the rural Niagara West—Glanbrook riding, where he would have faced a difficult battle with a candidate of the Conservative Party of Canada.

He therefore decided to run in the western half of his former riding, resulting in a passionate nomination battle with former cabinet heavyweight and party leadership candidate Sheila Copps. Some accused Martin of orchestrating these events to try to expel the left-leaning Copps from the House of Commons. On March 6, 2004, Valeri won the nomination by 311 votes. Stelco's economic troubles and the large pension deficit galvanized support for New Democratic Party (NDP) candidate Tony DePaulo in Hamilton East—Stoney Creek. The conflict with Copps, public reaction to the first budget of the Ontario Liberals, as well as the government's sinking fortunes, almost cost him his seat, but he was narrowly (less than 1,000 votes) re-elected on June 28, 2004.

Government House Leader

On July 20, 2004, he was appointed to the sensitive position of Government House Leader in Paul Martin's minority government. Valeri's appointment to the position of House Leader was originally questioned by many, however Valeri was able to establish a working relationship with his counterparts.

As noted by Libby Davies, NDP House Leader, "We had some crazy moments but we always got down to business in a real way. It was a pleasure to work with (Valeri)." Former Conservative House Leader John Reynolds noted that "Tony was a great House Leader. A man of integrity and good humour."

In his 2008 memoir, entitled Hell Or High Water: My Life In And Out of Politics (ISBN 0771056923), former Prime Minister Paul Martin labeled Valeri as “one of the most gifted House Leaders of recent times.”

2006 re-election bid

On January 23, 2006, Valeri was narrowly defeated by a margin of less than 500 votes by the New Democratic Party candidate Wayne Marston. During the election, the Hamilton Spectator reported that Valeri had purchased a property for $225,000 only to later sell it to a Liberal supporter for $500,000 a few months later. While Valeri insisted that the Ethics Commissioner had cleared the transaction, lingering doubts about the sale remained.