Nestoridis moved with his family to Kallithea, Athens at a very early age. His football career officially started at Panionios where he played until 1955. Prior to that he played for local club Ellas Moschato under an assumed name. He began his illustrious career at AEK in 1957, having sat out the 1956 season, as Panionios refused to negotiate his transfer to "Enosis".
Kapetan Nestoras started paying dividends almost immediately by winning top scorer honours in Greece for five consecutive seasons from 1958 - 1963 (the last regional championship played and the first four national competitions). Over all, he scored 224 goals in 250 matches for AEK. He played for them until 1966 at which point he joined newly-promoted Vyzas Megara FC for one year before retiring.
There is a book currently being written on the history of Greek-Australian soccer teams. It is a collection of mini-histories of some 100 past and present soccer clubs with Nestoridis featured in the history of the South Melbourne Hellas Soccer Club. Nestoridis won the 1966 Victorian State League championship for South Melbourne Hellas with his goalscoring exploits. He was a magnificent footballer with silky skills who troubled many defenders in 1966. He is still considered as the best Greek forward in a one-on-one situation with a keeper and frequently scored directly from corner kicks.
Nestoridis won top scoring honours 5 years in succession: