their home games during Gordon's time there, and he won praise for an outstanding performance in an away league match in Dumfries versus Queen of the South which ended 3–1. Divisional champions that season, Queens dominated the game, but Gordon's saves thwarted them time and again, with opposition manager John Connolly describing Gordon's performance as "sensational". Heart of Midlothian Gordon made his debut for Hearts in a 1–1 draw with Livingston on 6 October 2002. His one other appearance that season was in a 4–0 defeat against Falkirk on 25 January 2003 in the third round of the Scottish Cup. Over the course of the following season, 2003–04 season, he edged out Tepi Moilanen as the regular Hearts goalkeeper, playing in 29 of Hearts' league fixtures. Gordon made his first appearance in European competition on 6 November 2003, playing in the first leg of Hearts' UEFA Cup second round tie in France against Bordeaux. He performed well and kept a clean sheet in an impressive 1–0 win for Hearts. Despite that result, Heart lost the return leg 2–0 in Edinburgh to go out on aggregate. His performances that year resulted in him being short-listed for the Scottish PFA Young Player of the Year award, which was eventually won by then Celtic midfielder Stephen Pearson. Gordon did win SFWA Young Player of the Year and SPL Young Player of the Year accolades for 2003–04. He was selected as SPL Young Player of the Month too for December 2003. Manager Craig Levein praised Gordon for his performances, stating that he had a "brilliant" season and that whilst Levein initially only intended to play him in a handful of games, "he did so well that I couldn't take him out [of the first team]." Gordon signed a new three-year contract with the club in August 2004. In his first full season as first choice goalkeeper, Hearts qualified for the UEFA Cup after they finished third behind champions Celtic and Rangers. The team qualified for the group stages of the UEFA Cup beating Braga on aggregate 5–3. Hearts also reached the semi finals of both the Scottish Cup (beaten by Motherwell after extra time) and Scottish League Cup (beaten by Celtic) in season 2004–05. Gordon had become a Scotland regular by 2005 and his consistent displays during the 2005–06 season helped Hearts to a second-place finish in the Scottish Premier League and victory in