Albanija je prvič nastopila na Pesmi Evrovizije leta 2004. Kot debitantka je s predstavnico Anjezo Shanini in s pesmijo The image of you zasedla 7. mesto. Ker se je leta 2004 torej uvrstila med prvih deset držav, je smela na Pesmi Evrovizije 2005 nastopiti neposredno v finalu; tokrat jo je zastopala Ledina Çelo s pesmijo Tomorrow I go ter zasedla v polfinalu 16. mesto. Zatorej se je albanski predstavnik Luiz Ejlli moral na Evroviziji 2006 s pesmijo Zjarr E Ftohtë pomeriti najprej v polfinalu. Leta 2006 je Albanijo prvič predstavljal moški in njihova pesem je bila prvič odpeta v albanščini. Doslej najslabšo uvrstitev je Albanija doživela na Evroviziji 2007, kjer je zasedla šele 17. mesto v polfinalu.