Anfänge beim FC Sion

1991 zog Fernandes als Fünfjähriger gemeinsam mit seiner Mutter aus der Hauptstadt der Kapverdischen Inseln nach Sitten in die Schweiz, da sein Vater dort Arbeit gefunden hatte. Beim FC Sion begann er, Fussball zu spielen und durchlief alle Jugendabteilungen. Von 2004 bis 2007 gehörte er dem Profikader des Vereins an. 2004 bis 2006 bestritt er 65 Zweitligaspiele, 2006/07 – aufstiegsbedingt – 34 Erstligaspiele. Sein Erstligadebüt gab er am 19. Juli 2006 (1. Spieltag) beim torlosen Remis im Auswärtsspiel gegen den Grasshopper Club Zürich, sein einziges Erstligator gelang ihm am 14. Oktober 2006 (11. Spieltag) mit dem Treffer zum 1:1-Endstand in der 90. Minute im Auswärtsspiel gegen den FC Luzern.

Manchester City und Saint-Étienne

Zur Saison 2007/08 wechselte Fernandes zum englischen Erstligisten Manchester City. Die Transfersumme von 9,1 Millionen Franken war seinerzeit die zweithöchste, die je von einem ausländischen Verein für einen Schweizer Spieler gezahlt wurde. Nachdem er 2007/08 nur zu vereinzelten Teileinsätzen gekommen war, konnte sich Fernandes in Manchester einen Stammplatz erarbeiten und spielte dort meist an der Seite des Routiniers Dietmar Hamann.

Zur Saison 2009/10 wechselte Fernandes zum französischen Erstligisten AS Saint-Étienne, für den er 33 Ligaspiele bestritt.

Leihspieler in Verona, Leicester und Udine

Zur Saison 2010/11 wechselte Fernandes – auf Leihbasis – zum italienischen Erstligisten Chievo Verona und erzielte in 29 Einsätzen zwei Tore. Am 12. September 2010 (2. Spieltag) debütierte er beim 3:1-Sieg im Auswärtsspiel gegen den CFC Genua; sein erstes Ligator erzielte er am 22. September 2010 (4. Spieltag) beim 3:1-Sieg im Auswärtsspiel gegen den SSC Neapel mit dem Treffer zum zwischenzeitlichen 2:1 in der 58. Minute.

Zu Beginn der Saison 2011/12 wechselte er – erneut auf Leihbasis – zum englischen Zweitligisten Leicester City. Sein einziges Ligator in 15 Ligaeinsätzen gelang ihm am 20. August 2011 (11. Spieltag) beim 2:2-Unentschieden im Auswärtsspiel gegen Nottingham Forest mit dem Treffer zum zwischenzeitlichen 2:0 in der 21. Minute.

In der Winterpause folgte eine weitere Leihvereinbarung mit dem italienischen Erstligisten Udinese Calcio, der am Ende der Spielzeit die Kaufoption ungenutzt liess.

Sporting Lissabon und FC Sion

In der Sommerpause 2012 wurde der noch bis 2013 gültige Vertrag zwischen Saint-Étienne und Fernandes aufgelöst. Fernandes unterschrieb daraufhin beim portugiesischen Erstligisten Sporting Lissabon einen Vierjahresvertrag; bestritt aber lediglich sechs Ligaspiele. Im Dezember 2012 wurde bekannt, dass er für anderthalb Jahre als Leihgabe zum FC Sion zurückkehren werde.

Bundesliga und drei Jahre Rennes

Zur Saison 2013/14 wechselte er zum Bundesligisten SC Freiburg. Für diesen absolvierte er 38 Spiele und erzielte ein Tor. Er wurde in 30 Spielen in der Bundesliga eingesetzt, sowie 5 Spiele in der Europa League und 3 Spiele im DFB-Pokal.

Nach einer Saison beim SC Freiburg wechselte Fernandes im August 2014 in die Ligue 1 zu Stade Rennes.

Rückkehr in die Bundesliga

Zur Saison 2017/18 wechselte Fernandes zum Bundesligisten Eintracht Frankfurt, bei dem er einen Zweijahresvertrag unterschrieb. Im Mai 2018 gewann der Schweizer mit der Mannschaft nach einem 3:1-Finalsieg gegen den FC Bayern München den DFB-Pokal. Im Dezember desselben Jahres wurde sein Vertrag bis Juni 2020 verlängert. In der Spielzeit 2018/19 drang er mit der Eintracht bis ins Halbfinale der Europa League vor und scheiterte mit seiner Mannschaft dort im Elfmeterschießen am FC Chelsea; Fernandes wurde im Wettbewerb neunmal eingesetzt. Insgesamt stand der Schweizer für die Frankfurter in 81 Pflichtspielen auf dem Feld. Mit dem Ende der Bundesliga-Spielzeit 2019/20 beendete Fernandes seine aktive Karriere.