Prvu zvaničnu utakmicu Albanija i Bosna i Hercegovina odigrali su 30. novembra 1995. godine u Tirani. Ovo je ujedno bila i prva zvanična utakmica nogometne reprezentacije Bosne i Hercegovine nakon proglašavanja nezavisnosti Bosne i Hercegovine i otcjepljenja od Jugoslavije. Golovima Anestia Qendra i Enkeleid Dobija Albanija je bila uspješnija. Već narednu utakmicu Albanija i Bosna i Hercegovina odigrali su 24. aprila 1996. u Zenici. Utakmica je završila bez postignutih golova. U sklopu kvalifikacija za Evropsko prvenstvo 2012. Albanija i Bosna i Hercegovina odigrali su dvije utakmice. U Tirani, 8. oktobra 2010, golovima Vedada Ibiševića u 21. i Klodiana Dure u 45. minuti utakmice završena je prva kvalifikacijska utakmica pomenutih reprezentacija. U Zenici 7. juna 2011. Bosna i Hercegovina je golovima Harisa Medunjanina u 67. i Darka Maletića u 90. minuti utakmice bila uspješnija rezultatom 2–0. 28. marta 2017. u Elbasanu, u prijateljskoj utakmici Bosna i Hercegovina je bila uspješnija od domaćina rezultatom 2–1. Golove za Bosnu i Hercegovinu postigli su Edin Džeko u 7. minuti utakmice iz jedanaesterca i Senad Lulić u 42. minuti utakmice nakon asistencije debitanta za nacionalnu selekciju Kenana Kodre. Jedini gol za Albaniju postigao je Bekim Balaj u 68. minuti utakmice. Osim Kenana Kodre u ovoj utakmice za Bosnu i Hercegovinu debitovao je i Dario Đumić koji je odigrao cijelu utakmicu.