Seine Karriere begann Fotsis bei Ilisiakos Athens Nachwuchsmannschaft, bevor er 1997 zum griechischen Rekordmeister Panathinaikos Athen wechselte. Bei Panathinaikos konnte Fotsis in den folgenden Jahren seine ersten Profititel gewinnen und schaffte den Sprung in die Nationalmannschaft. Im Jahr 2001 wurde er an 48. Stelle der NBA-Drafts von den Memphis Grizzlies ausgewählt und wechselte in die NBA. Fotsis wurde damit der erste Grieche in der NBA, der auch in Griechenland geboren wurde. Nach nur einer Saison wechselte der Power Forward 2002 schließlich wieder zu Panathinaikos Athen, wo er das Double gewinnen konnte. Nach einer Saison in Spanien und gewonnener Meisterschaft mit Real Madrid wechselte Fotsis 2004 zu Dynamo Moskau, wo er den ULEB Cup gewinnen konnte. Im Sommer 2008 unterzeichnete Fotsis bei Panathinaikos einen Dreijahresvertrag und wechselte zum dritten Mal in seiner Laufbahn zum griechischen Rekordmeister.
Nationalmannschaft
Mit der griechischen Nationalmannschaft gewann Fotsis 2005 die Basketball-Europameisterschaft. Gegner im Finale, das in Belgrad stattfand, war die deutsche Mannschaft. Bei der Basketball-Weltmeisterschaft 2006 erreichte Fotsis mit Griechenland das Finale und gewann dort die Silbermedaille. Zwischen 2009 und 2014 war Fotsis griechischer Mannschaftskapitän.
