Born in Drama of Pontian Greek heritage, his family moved to Athens in his youth. Nestoridis began playing youth football with Enosis Ag. Nikolaos Kallithea in 1945, and began playing senior football with Panionios G.S.S. in 1947 at age 17. Nestoridis played for Panionios until 1955, and he began an illustrious career at AEK Athens F.C. in 1957, having sat out the 1956 season because Panionios refused to negotiate his transfer to AEK.
"Kapetan (Captain) Nestoras" started paying dividends almost immediately by winning top scorer honours in Greece for five consecutive seasons from 1958 up until 1963 (the last regional championship played and the first four national competitions). In total he scored 223 goals in 265 games for AEK, and remains one of the club's highest scoring players of all time, widely regarded by the club's fans as one of the greatest players to ever wear the AEK shirt. He remains the third highest league scorer for AEK, having scored a total of 172 goals in 202 games in the Greek domestic league.He and another AEK Athens' legend, Mimis Papaioannou were one of club's best scoring couple of the club and most beloved. He played for AEK until December 1965 at which point he joined newly promoted Vyzas F.C. for one year before retiring.
He took a break from the Greek League in 1966 to play for South Melbourne Hellas where, at age 36, he won top scorer honors yet again, helping the club to the Victorian State League title. Nestoridis rejoined South Melbourne Hellas in 1967 where his team finished 4th in the league competition. His last game for Hellas was in the Dockerty Cup final losing 0-4 to Port Melbourne Slavia. During his two years in Melbourne, Nestoridis drew big crowds where ever Hellas played.
After his playing career was over, Nestoridis coached several clubs including Paniliakos FC, Kallithea FC and AEK (1982 and 1983).