After the defeat of the Keating government in 1996, Faulkner became Leader of the Opposition in the Senate, and was a member of the Opposition Shadow Ministry 1996–2004. He was at various times Shadow Minister for Social Security, Public Administration and Home Affairs. He was a key Labor strategist in the 1998, 2001 and 2004 federal elections, and was a particularly close advisor to Mark Latham during the 2004 election. In the wake of Labor's defeat in that election, he resigned his positions. Faulkner became the first Labor Senate leader who did not become Government Senate leader since Don Willesee.