Fernandes iddebutta mat-tim nazzjonali Żvizzeru kontra l-Olanda fit-22 ta' Awwissu, 2007. Minn dakinhar baqa' figura regulari mat-tim nazzjonali. Hu lagħab fit-tliet partiti tat-tim waqt il-Kampjonati Ewropej 2008. Nhar it-28 ta' Marzu, 2009, Fernandes skorja l-ewwel gowl tiegħu fuq livell internazzjonali fir-rebħa ta' 2–0 fuq il-Moldova. It-tieni gowl wasal fuq palk iktar prestiġjuż, hekk kif skorja l-gowl tar-rebħa kontra Spanja fl-ewwel logħba mill-gruppi tat-Tazza tad-Dinja 2010.