He won thirty-fourth place on the Likud-Gesher-Tzomet list for the 1996 elections, but missed out on a place in the Knesset when the alliance won only 32 seats. However, he entered the Knesset in November 1998 as a replacement for Ehud Olmert. He was re-elected in 1999 and 2003, and was appointed Minister of Agriculture in Ariel Sharon's government in 2003. Katz left the cabinet in January 2006 after the Likud-Kadima split, and was re-elected in the 2006 elections.
In 2007 the Israel Police recommended indicting Katz on charges of fraud and breach of trust linked to political appointments at the Ministry of Agriculture during his tenure as minister.
Katz retained his seat again in the 2009 elections after winning eleventh place on the Likud list, and was appointed Minister of Transportation in the Netanyahu government.