[2] After two years with the Dark Blues, making 59 appearances and scoring four goals in all competitions, Fotheringham moved to Germany with SC Freiburg, where he played for a season.
After an unsuccessful trial with Leeds United,[3] Fotheringham moved to FC Aarau of the Swiss Super League in 2006 but left midway through the season.
The 2007–08 season began well for Fotheringham, as he scored his first goal for the club in a 5–2 League Cup win over Barnet.
[4] It was also confirmed that he would remain as club captain, however a number of other players including Darel Russell and Gary Doherty filled this role in his periods of absence from the team during the season.
In March 2009, following an incident where he stormed down the Carrow Road tunnel having been substituted in a match against Coventry City, Fotheringham was stripped of his captaincy role to be permanently replaced by Doherty.
At the end of the 2010–11 season, Manager Stanimir Stoilov then froze him out of for the pre-season training by banning him from entering the club's facilities.
[22] After making thirteen appearances, Fotheringham left Ross County to join Swiss side Luzern.
[25] Fotheringham played 34 matches for County before signing for Fulham in August 2014, joining a side who had recently been relegated into the Championship after 13 seasons in the Premier League.
Tomas Oral, head coach of German side Karlsruher SC, knew Fotheringham from his time as assistant to Felix Magath at Fulham.
He left Cowdenbeath in 2019 and returned to Germany, again as assistant coach of Oral at German 2nd tier club FC Ingolstadt 04.