Anastasakos speelde eerder voor Asteras Tripolis, Apollon Athene, Kalamata FC, AEK Athene en Thrasivoulos Filis voordat hij in 2008 naar PAOK Saloniki kwam. Hij was topscorer van de Beta Ethniki (Het Grieks equivalent van de Nederlandse Eerste divisie, of de tweede hoogste voetbalklasse) toen PAOK hem overnam van Thrasivoulos Filis.
Ook bij PAOK Saloniki scoorde hij regelmatig. Toch waren er twijfels met name in de Griekse pers of hij het niveau wel aan kon. Zijn doelpunt in de oefenwedstrijd tegen Willem II ter voorbereiding op het nieuwe seizoen, was mede daarom een hele bevrijding.
