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.

Although dropped by new manager Paul Lambert early on in the 2009/10 season, he fought his way back into the first team (due to injuries for the clash with Leyton Orient which City won 4-0), made himself first choice defender and ended the season voted third in the Player of the Year award. He made 44 appearances and scored 7 goals. However he was released by the club on 14th May 2010 following their promotion to the Championship. He was soon linked with a switch to Malky Mackay's Watford

After media reports linking him with Greek side iraklis, Doherty signed a two year deal with Charlton on 6th July 2010. Addicks boss Phil Parkinson said: “He's an experienced centre-back with great quality and I'm delighted he's agreed to join us. Of all the centre-backs out there in the summer he was the one I targeted. It's taken a while to do the deal for various reasons. From day one, Gary expressed his interest in coming to Charlton. He wants to be a part of what we hope is going to be a successful season.”