On 18th August 2004, Norwich announced that they had agreed with Tottenham to sign their Irish utility player Gary Doherty who not fit into Jacques Santini's plans. Although away with the Irish Republic on international duty, Norwich completed the signing on 20th August and Gary made an impressive debut the following day as substitute at Manchester United. His full debut for Norwich came four days later at Newcastle where he scored City's second goal in 2-2 draw.

Although his Canaries career started well, he soon found himself out of the starting XI which led to speculation in November 2004 that he was to join Sheffield United.

Gary became his career at Luton Town before joining Spurs in 2000 for £1million

After Norwich's relegation to the Championship in May 2005, Gary was linked with a switch to newly promoted Sunderland. He stayed at Carrow Road and was named Player of the Year for the 2005/6 season

Out of contract at the end of the 2007/8 season, Gary was in talks with Major League Soccer side San Jose Earthquakes according to reports in the San Jose press. "The Earthquakes are talking to Norwich City defender Gary Doherty about a possible move to San Jose," the paper said. "General Manager John Doyle said today the talks are in the early stages; the team has been looking at a number of players to try to bolster its line-up and preliminary talks with players often don't lead to a signing." In the end, Doherty signed a new two year contract with the Canaries.