Mientras su padre desarrollaba su carrera como músico en Alemania, Leandros permaneció en el hogar de su abuela paterna hasta la edad de cinco años.