Впервые Албания начала этот путь с достойного и уникального участия Аньезы Шахини в 2004 году с песней «Your Image». Песня была исполнена на английском языке под названием «The Image Of You» с музыкой Эдмона Жулали и текстами Агима Доси. Она квалифицировалась в финал, где получила 106 очков, заняв 7-е место среди 24 конкурентных стран. Это был хороший старт для Албании как участника музыкального конкурса за пределами своей территории.
Победительницей 43-го Песенного фестиваля стала Ледина Чело с песней «Nesër shkoj». Чело не смогла превзойти 7-е место Аньезы Шахини, её оценили всего с 53 баллами, и она заняла 16-е место в финале — песня с ритмами, исполненная на английском и с магическим исполнением.
Победитель 44-го Песенного фестиваля, Луис Эйлли, выступил с песней «Zjarr e Ftohtë» и стал первым албанским участником на Евровидении, исполненным на албанском языке. В полуфинале 2006 года он получил 58 очков и был назван первым неудачником Албании, так как в том году не вышел в финал. Песня с особенными народными мотивами, но им понравилось.
В 2007 году это был Фредерик Ндочи с песней «Hear My Plea», победитель 45-го фестиваля песни. На албанском языке она известна как «Баллада о камне». Песня на Евровидении была исполнена на английском и албанском языках. В полуфинале 2007 года песня получила 49 очков и снова провалилась после неудачи в финал.
