Gardner groeide op in de buurt van Yardley en voltooide de Cockshut Hill Technology College. Hij werd prof op 31 januari2005. Voordat Gardner zijn debuut maakte in de Premier League met Aston Villa op 26 december2005, speelde hij in het jeugdteam van Yardley Kings. Hij maakte zijn debuut toen hij er in kwam als wisselspeler voor Steven Davis tegen Everton op Villa Park. Gardner scoorde zijn eerste doelpunt voor Aston Villa in de 3-1-overwinning op Middlesbrough op 14 april. Ook maakte hij een mooie goal tegen Bolton Wanderers, het werd zelfs bekroond met doelpunt van de maand. Samen met teamgenoot Gabriel Agbonlahor groeide Gardner uit tot een van de favoriete spelers bij het publiek van Aston Villa. Na een serie goede prestaties bood Martin O'Neill Gardner een contract aan, dat hem verbond tot juli 2011.
In oktober 2007 scoorde Gardner doelpunten uit vrije trappen in twee achtereenvolgende wedstrijden. Eerst in het 4-4 gelijkspel tegen Tottenham Hotspur en een week later in de 5-1-overwinning tegen West Ham United.
Op 1 december2007 scoorde Gardner de openingstreffer tegen Arsenal, maar Villa verloor alsnog met 2-1. Omdat Aston Villa te weinig kwaliteit had achterin, moest Gardner vaak als rechtsback optreden. In september 2008 tekende Gardner een contract tot medio 2012.
Vanaf het seizoen 2008/2009 had hij geen basisplaats meer bij de club. In januari 2010 tekende hij daarom bij Birmingham City. Na het seizoen 2010-2011, waarin hij acht doelpunten scoorde in 29 wedstrijden, tekende hij bij Sunderland AFC.