Starting his career with Port Vale in 1998, within two years he earned a £1 million move to Tottenham Hotspur. He spent eight years at the Premier League club, making 142 appearances in all competitions. In 2008. he spent time on loan at both Everton and Hull City, before signing permanently with the latter that summer for £2.5 million. He spent the 2010–11 season on loan at Crystal Palace, before joining the club permanently the next season. He signed with Sheffield Wednesday in June 2012, and stayed with the club for two years.
Born in Stone, Staffordshire, Gardner started his career with First Division club Port Vale after signing associate schoolboy forms in 1997. He signed his first professional contract on 31 July 1998. He made his first-team debut under John Rudge in October of the 1998–99 season. He scored his first senior goal on 1 May 1999, in a 2–0 win over Queens Park Rangers. He made 15 league appearances in 1998–99.
He made 29 appearances in 1999–2000 under new manager Brian Horton, scoring goals at Queens Park Rangers, Huddersfield Town and Sheffield United. At the end of the season, Vale were relegated into the Second Division, but by that time Gardner had already left the club.
Gardner signed for George Graham's Tottenham Hotspur in January 2000 for a £1 million fee. He worked his way up through the reserve team before making his debut as a substitute against Derby County in March 2001. He finished 2000–01 with eight appearances. However, he suffered knee ligament damage at the back end of the season which ruled him out until December. He played 19 matches in 2001–02.
Gardner scored his first goal for Tottenham in a 3–2 victory over local rivals West Ham United in September 2002. However, he was limited to just 13 appearances in 2002–03. He managed to play 40 matches in 2003–04, with 33 of these matches being in the Premier League. He scored his second Tottenham goal in a League Cup tie against Oldham Athletic on 22 September 2004. However, he made just 17 league appearances in 2004–05. Injury restricted him to just 17 league matches again in 2005–06, and made just 16 appearances in 2006–07, of which eight were in the league.
At the beginning of 2007–08, Gardner found himself on the teamsheet due to the ongoing injuries of Ledley King and Michael Dawson. He managed to make an impact – in vain – by scoring his team's only goal in their second Premier League match of the season at home to Everton on 15 August 2007, which Tottenham lost 3–1. On 25 October, he was injured playing against Getafe in the UEFA Cup. He was stretchered off with a suspected broken ankle in the 42nd minute. On 31 January 2008, Gardner signed for Tottenham's Premier League rivals Everton on loan for the remainder of the season, but did not make a single appearance. Over the course of the season, he played just six competitive matches for Tottenham.
Gardner was loaned to Premier League newcomers Hull City at the start of 2008–09. The initial deal was to last until January 2009, but Hull had the option of purchasing him at any point during the loan period. Hull exercised their purchase option to make the loan move permanent in August for a £2.5 million fee, which at the time was a club record signing. On 23 March 2009, it was revealed that Gardner would miss the remainder of the season after x-rays revealed four fractured vertebrae in the base of his spine. The injury was sustained in the 2–1 defeat to Arsenal in the FA Cup at the Emirates Stadium six days earlier. Hull avoided relegation, however Gardner only played eight matches in 2008–09.
Gardner played 24 matches in 2009–10, as Hull suffered relegation into the Championship after finishing in 19th place. He made a further three appearances in 2010–11, before leaving the club.
On 31 August 2010, he joined Crystal Palace on a five-month loan deal, which was later extended to the end of the season. He scored his first goal for Palace in a 2–1 win at Norwich City on 19 October. Gardner made 28 Championship appearances for Palace over the course of the season. At the end of the season, Gardner was not offered a new contract by Hull. This allowed him to sign for Palace on a one-year contract in August 2011.
Gardner was then an important part of Crystal Palace's defence in 2011–12. He played all 120 minutes of Palace's "stunning extra-time victory at Old Trafford" on 30 November 2011, as they defeated Premier League champions Manchester United 2–1 to reach the semi-final of the League Cup. He scored with his head for the home team at both Selhurst Park and the Cardiff City Stadium in the semi-final, leaving the tie level at 1–1 after two legs; Cardiff City won the subsequent penalty shoot-out to deny Palace a place at the final. Gardner was short-listed for the club's Player of the Year award at the end of the season, though the award instead went to fellow defender Jonathan Parr. Palace offered him a new contract, but it quickly became apparent that Gardner would instead be moving to a new club.
He signed a two-year contract with Championship newcomers Sheffield Wednesday on 20 June 2012; manager Dave Jones said that he "is a quality player and a leader, with Championship and Premiership pedigree". He made his Wednesday debut on 13 August, in a 4–2 League Cup win over Oldham Athletic. He made 38 appearances in 2012–13, and was twice named on the Championship Team of the Week.
Gardner played six matches before being ruled out for 2013–14 after requiring surgery on an Achilles injury in September. He was released by new manager Stuart Gray in May 2014.
Gardner represented England at under-21 level, gaining one cap under David Platt.
Gardner began to impress during 2003–04, and earned his England call-up as cover for Gareth Southgate in a friendly against Denmark in March 2004. He won his first and only England cap against Sweden on 31 March 2004, after Sven-Göran Eriksson used him as a half-time substitute for John Terry.
His cousin, Jordan Fincher, took part in Sky1's Football's Next Star in 2010.