Haxhi speelde in de periode 1995-2009 in totaal 68 interlands voor het Albanese nationale team en scoorde drie keer. Hij maakte zijn debuut voor de nationale ploeg op 30 november1995 in de vriendschappelijke thuiswedstrijd tegen Bosnië-Herzegovina (2-0). Haxhi werd in dat duel na 55 minuten vervangen door Enkelejd Dobi.