En los años 80 Eleftheria conoce a la Opisthodromiki Kompania, un grupo de estudiantes y músicos aficionados que ayudaron a la rembetika y la smyrneika, a ocupar un lugar dentro de la escena de la música griega. La rembetika y la smyrneika son canciones de los refugiados griegos en Asia menor y data de los años 20 y 30, que fue redescubierta por la Opisthodromiki Kompania, que tambien tocaba laika. La Opisthodromiki Kompania con Eleftheria Arvanitaki como cantante grabó 3 discos y dio una serie de conciertos en Grecia.

Al dejar la Opisthodromiki Kompania en 1985, ella decidió continuar como solista, y rápidamente se estableció como una de las voces femeninas mas prometedoras. Su cualidades vocales y su ambición por salvar el vacio existente entre la música tradicional griega y la estética de las canciones urbanas contemporáneas, llevaron a algunos de los mas distinguidos poetas contemporáneos, como Michalis Ganas y Yannis Loannou, letristas como, Lina Nikolakopoulou, Manolis Rassoulis, Tasos Samartzis y Thodoris Gonis, y compositores como Dionissis Savopoulos, Nikos Mamagakis, Nikos Xidakis, St. Spanoudakis, Yiorgos Zikas, St. Kougioumtzis, Chr Nikolopoulos, Antonis Mitzelos y Dimitris Papadimitriou, que trabajaron para ayudar a crear el carácter de la escena de la música griega, confiando en Eleftheria y escribiendo canciones para ella, que son consideradas clásicos de la música griega.

Su primer álbum en solitario, en el que continuó cantando rembetika, laika y smyrneika, fue lanzado en 1984.  Entonces, ella conoció a Stamatis Spanoudakis, un joven y talentoso letrista, con quien grabó Kontrabando, que fué publicado en 1986.  Con Kontrabando, que fue considerado uno de los albumes mas innovadores de los 80, la carrera de Eleftheria despegó a nuevos niveles.  Su colaboración con Stamatis Spanoudakis continuo y tuvo sus resultados en un nuevo álbum titulado Tanirama, que vio la luz en 1989.

Le siguió otro gran álbum  en 1987.  Fue Konta sti doxa mia stigmi del compositor Nikos Xidakis, que es considerado un de los pilares de la música moderna griega.  La colaboración de Eleftheria con Nikos Xidakis continúa y da como resultado una serie de grandes albumes como Tenedos (1991), To Meli ton gremon (1994) y Akroterio Tenaron (1997).

1991 es un punto destacado en la carrera de Eleftheria Arvanitaki, se publica su  album Meno Ektos.  Varios compositores, incluidos, Y. Zikas, Chr. Nikolopoulos, N. Xidakis, A. Mitzelos, Ara Dinkjian y los letristas Lina Nikolakopoulou y Th. Gonis escribieron las canciones del álbum que combina influencias del este y de los Balcanes, con elementos de la música electrónica, dos de esas canciones destacaron y siguen siendo consideradas dos de sus mejores canciones; Dinata y Meno Ektos, escritas ambas por Ara Dinkjian.  Este álbum tuvo un inmenso éxito comercial y llegó a platino, pero también determinó la carrera de Eleftheria Arvanitaki en los años siguientes.

En 1993 grabó un álbum en directo, I Nichta Katevenei, durante una serie de conciertos en el Apollo Concert Hall de Atenas, también grabó  Anastasia de Dimitris Papadimitriou, música para una serie de televisión muy popular.

En 1994 Eleftheria Arvanitaki se consagró como una de las mas grandes estrellas en Grecia.  Meno Ektos, I Nichta Katevenei y Anastasia ocuparon un lugar en el Top Ten durante un año, mientras tenía enorme éxito en sus conciertos en Grecia y Chipre.