Fontaine, who was a youth player at Fulham, represented England at under-16 and under-17 level. Fontaine spent some time at Yeovil Town in the first part of the 2004–05 season. His loan move was initially for a single month, but was later extended by a further two months. He made a couple of first team appearances for Fulham in January 2005. His debut came in a Premier League game against Southampton at St. Mary's on 5 January, which was drawn 3–3. He enjoyed a further loan spell in the latter part of the 2004–05 season with Kilmarnock in the Scottish Premier League.
Bristol City
After being brought to Yeovil by then manager Gary Johnson, Fontaine then went back to Fulham until he was brought to Bristol City on loan by his former Yeovil manager Johnson. The loan spell was made permanent at the end of that season with Fontaine signing a two-year contract, with City having to pay Fulham an undisclosed fee through tribunal. A key member of the 2006–07 promotion team and flourished once more at Championship level, he became centre stage when his goal against Wolves in November left his manager Gary Johnson red-faced – having previously told his defender he would "bare my backside in Burton's window" if he found the net. Fontaine signed a new deal with Bristol City on 12 January 2012 to keep him at the club until the end of 2014 season, stating his ambition is to be the club's captain on a permanent basis. On 2 September 2013, Fontaine joined Championship side Yeovil Town, for a third spell, on loan until January 2014. At the end of the 2013–14 season, Fontaine was released by Bristol City.
Hibernian
On 26 August 2014, Fontaine joined Scottish Championship side Hibernian. He made his debut the same day, in Hibernian's 3–2 victory against Dumbarton in the Scottish League Cup. Fontaine made 38 appearances and scored two goals in the 2014–15 season. In June 2015, he signed a two-year contract with Hibernian. He scored a goal in the March 2016 Scottish League Cup Final, which Hibs lost 2–1 to Ross County. Fontaine played the first 70 minutes of the 2016 Scottish Cup Final, which Hibs won 3–2 against Rangers. In June 2017, Fontaine signed a contract with Hibs for the 2017–18 season. He suffered an ankle injury playing for the Hibs under-20 side in September 2017, which head coachNeil Lennon said would prevent Fontaine from playing for at least 10 weeks.
