In augustus 2010 werd hij uitgenodigd om bij de wedstrijd PAOK Saloniki - Ajax te zijn. Anastasiou zag Ajax winnen en sprak uit dat hij nog steeds een groot Ajax fan is. [1]
Een paar maanden later liep Anastasiou zes weken stage bij Jong Ajax om zijn trainers diploma af te ronden. Na zijn stage werd hij gecontracteerd om de rest van het seizoen 2010/11 assistent-trainer te zijn bij het Jong Ajax van Gery Vink. [2] Door de hervormingen van de jeugdopleiding tijdens de Fluwelen Revolutie (2010-12) kreeg Anastasiou het seizoen daarna de Ajax B2 in handen. Het seizoen daarop vertrok hij echter naar Roda JC, om daar het belofte elftal te gaan trainen.