Anastasiadis began his career at Heidelberg United before being signed by the Greek club PAOK Thessaloniki FC at the age of 19. He made his debut in 1988 and became an influential part of the team, playing in 18 Alpha Ethniki matches, 5 cup games and 24 friendlies in the 1988/89 season, scoring 12 goals in total. He also took part in the club's brief 1990/91 and 1991/92 UEFA Cup campaigns. Anastasiadis played a total of 382 matches and scored 66 goals in his nine years at the club as a striker. Anastasiadis left PAOK in 1997 to return to Australia, where he joined NSL side South Melbourne FC. He played a key attacking role which helped the club to win back-to-back championships in the 1997/98 and 1998/99 seasons, scoring goals in both grand final victories: once in the 1997/98 final, past his brother Dean Anastasiadis who was in goal for Carlton; and two goals in the 1998/99 Grand Final against Sydney United as a substitute. He also represented the club at the 2000 FIFA Club World Championship, scoring the team's only goal of the competition against Mexican side Necaxa. He played his last professional game in the 2000/01 NSL grand final against the Wollongong Wolves, coming off the bench to score a goal, once again past his brother Dean who was in goal for the opposition. He finished his playing career fully in 2003 playing in the lower Victorian leagues with Yarraville Glory, as captain-coach. John Anastasiadis is an Honorary Life Member of , The official PAOK Thessaloniki Supporters Club of Australia.
Managerial career
After retirement from playing, and with Yarraville relegated under his stewardship in 2003, he managed to get the side promoted back the next season. In 2005, with the return of South Melbourne to the Victorian Premier League after the disbandment of the NSL competition, Anastasiadis put his hand up for the job which few wanted. Despite taking charge of a young squad which was quickly assembled merely weeks before the start of the new season, and which was labelled as a relegation candidate at the start of the year, Anastasiadis led the side to 3rd place on the ladder at the end of the season and as far as the Preliminary Final, where the team lost 1-0 to Heidelberg United and was knocked out. It was an incredible achievement for Anastasiadis considering just three players turned up to his first training session at the club, one of which was his brother Dean. Retained as coach for the 2006 season, he led South Melbourne to victory in the Grand Final of the Vodafone Cup competition. After failing to make the finals in 2007, South's poor start in 2008 saw Anastasiadis resign. After three years at South, John moved to the Oakleigh Cannons where he would spend the next three seasons. Despite mixed results, players such as Ivan Franjic. Cameron Watson and Nick Kalmar all came to prominence and earned A-League contracts. Anastasiadis departed Oakleigh in 2010. Half way through the 2011 season, Anastasiadis accepted a call from Bentleigh Greens to become the senior head coach. Since the move to Bentleigh, John has seen his team reach the VPL grand final in 2013, the semi-final of the inaugural FFA Cup in 2014 and win the club's first ever major title when Bentleigh beat South Melbourne FC at Lakeside Stadium in the National Premier Leagues Victoria Grand Final. Anastasiadis continued the success with Bentleigh winning the FFV Community Shield, beating foes South Melbourne FC at Kingston Heath Soccer Complex 3–0, the 2016 Dockerty Cup, the second major trophy in its history and first Dockerty Cup title, with a 1–0 victory over Green Gully SC, and just four days later, picked up the third piece of silverware for 2016, winning the NPL Victoria minor premiership for the first time in the club's history. Anastasiadis completed his AFC/FFA B Accredited Coaching Course in 2011, and is due to complete his AFC/FFA A Accredited Coaching Course in 2015. On 11 January 2019, Anastasiadis was announced as newly-formed A-League side Western United's inaugural senior assistant coach.
