He started playing with PAOK's youth team at the age of 13. Three years later he joins PAOK's third team which consisted primarily of teens. One year later he advanced to PAOK's first team along with team players Giannelos and Havanidis. His first game for the first team of PAOK was a friendly game against the Army National team (Εθνική Ενόπλων. He scored two goals in that game and PAOK won 4-0. His first official championship game was against Apollon Athens where he scored his first goal for PAOK in a championship game. In 1955-56 he is called to play with the Under 21 National team.
From 1957 until 1969 when he retired, he was the captain of the team, wearing number 7. He scored more than 80 goals for PAOK.
Leandros was capped 6 times by the Greek National Football Team during his career.
After retirement, he continued working with the management team of PAOK and established a Youth Academy at PAOK (the Academy later in 1974 sprung players like Alavantas, Alexandridis, Skounas, Siggas).