Fotakis speelde de eerste jaren van zijn carrière in zijn vaderland, voor PAOK Saloniki, Kallithea en Egaleo. In januari 2006 verhuisde hij naar Schotland om voor Kilmarnock te gaan spelen, maar hij kwam geen minuut in actie in de competitie. Hij keerde terug naar Griekenland in 2006 en via Larissa belandde hij in de zomer van 2009 bij PAOK Saloniki.