Gordon established himself as the Scotland first-choice goalkeeper throughout the campaign and under Vogts' successor Walter Smith, playing in all ten of Scotland's qualifying matches. BBC pundit and former player Allan Preston saw him as a potential Scottish great, describing him as "one of the best goalkeepers in Europe". After a 1–1 draw versus Italy, Gordon obtained praise from the opposition goalkeeper Gianluigi Buffon, who said he could be one of the best goalkeepers in the world. Gordon kept clean sheets as Scotland won 1–0 twice versus France in UEFA Euro 2008 qualification. He also registered an assist in the Parc de Princes, after McFadden controlled Gordon's punt, turned his marker and smashed home from 35 yards. Gordon had attained a total of 40 caps by November 2010 but his injury problems prevented him from adding to this total for the next four years. Following his comeback with Celtic, Gordon was recalled to the Scotland squad in September 2014 for a Euro 2016 qualification match against Germany. Gordon eventually obtained his 41st cap, ending a four-year absence from international football, when he came on as a half-time substitute in a friendly defeat to England on 18 November 2014. Gordon started his first Scotland match in almost five years in a friendly win versus Northern Ireland in March 2015 Gordon made his first start for Scotland in a competitive match in seven years in a 2018 World Cup qualifier against England in November 2016, and retained his place in the team for the 1–0 home win versus Slovenia in March 2017. On 5 October 2017, Gordon obtained his 50th cap versus Slovakia at Hampden Park to enter Scotland's Roll of Honour. Gordon was not selected by Scotland manager Steve Clarke during his first year in charge as he had lost his first team place at Celtic. After a good start to his second stint with Hearts, Gordon was recalled to the national squad in November 2020. The call up included the defeat of Serbia in the UEFA Nations League play-off final to qualify for UEFA Euro 2020, the Scotland men's team's first major tournament in 23 years. He also gained his 55th cap, a 1–0 away defeat by Slovakia in the 2020–21 UEFA Nations League, set a new record for the longest-spanning international career for a Scottish player (16 years 5 months and 17 days). This beat a mark set by