Nalitzis was born on January 25, 1976 in Piraeus. He began his senior career at Panionios in 1993. At Panionios, Nalitzis won the Greek Football Cup in 1998. In 2000, he won top scorer honours, playing the first half of the season at Panionios and the second half at PAOK Thessaloniki, becoming the only, so far, player to do so. The following year, he again won the Cup this time with PAOK.
|1998-1999 (on loan)||Ethnikos Asteras||13||6|
|2007-2008 (Dec)||Ethnikos Piraeus||50||8|