Gordon innledet sin karriere i skotsk fotball i Hearts. I sesongen 2001–2002 var han utlånt til Cowdenbeath på nivå 3, og Gordon etablerte seg som Hearts' førstekeeper i 2003 og bidro til at laget vant Scottish Cup i 2006. Han ble også den faste keeperen på Skottlands herrelandslag i fotball.
Den engelske Premier League-klubben Sunderland kjøpte Gordon i 2007 for £9 million,[6] noe som var den høyeste prisen en britisk klubb hadde betalt for en keeper. Gordon ble imidlertid i løpet av sin periode i Sunderland utsatt for alvorlige skader, og hans ble løst fra sin kontrakt i 2012.
Med en periode på to år uten å ha spilt en profesjonell kamp, skrev han kontrakt med Celtic i juli 2014.[7] Da Fraser Forster ble kjøpt av Southampton for £10 million i august samme år,[8] ble det åpnet for at Gordon kunne bli førstekeeper. Han spilte sin første tellende kamp på over to år 13. august 2014,[9] da Celtic vant 3-0 over St. Johnstone.[10]