Jens Stoltenberg është sekretari i gjashtë i përgjithshëm i NATO-s që viziton Shqipërinë në 25 vitet e fundit, pas rrëzimit të diktaturës komuniste. Qëndrimi i tij në Shqipëri, që pason atë në Bosnje më 7 dhe 8 dhjetor, vjen në kuadër të masave të vendeve te Ballkanit Perëndimor, për rritjen e sigurisë dhe stabilitetit në rajon. Shtetet në Ballkan janë edhe vendkalimet e para te refugjatëve sirian, rrugë këto që mund të përdoren dhe nga militantë të Shtetit Islamik. Që pas rënies së komunizmit, Shqipëria u vu në vëmendje të Aleancës së Atlantikut të Veriut. Shefi i parë i NATO-s që vizitoi Tiranën ishte Manfred Verner në maj të vitit 1993. Që në atë kohë, u miratua programi i parë i bashkëpunimit dhe Shqipëria hapi një kapitull të ri partneriteti.Gjate krizës së vitit 1997 në Shqipëri, NATO luajti një rol thelbësor për të frenuar përshkallëzimin e situatës në një lufte civile.Lufta e Kosovës shënoi momentin e parë më të madh të bashkëpunimit mes NATO-s dhe Shqipërisë. Nga marsi i ’98-ës, aleanca nisi zhvillimin e disa stërvitjeve te përbashkëta. Në 12 maj, Havier Solana mban vizitën e tij në Shqipëri, e dyta e një sekretari të përgjithshëm.Një muaj para zgjedhjeve parlamentare të qershorit 2001, shefi i ri i NATO-s Lord Robertson, zhvilloi vizitën e radhës në Shqipëri.Në maj të 2003, Shqipëria, Kroacia e Maqedonia nënshkruan Kartën e Adriatikut, dhe Shqipëria bashkëpunon dhe me misione ndërkombëtare deri në vitin 2008, kur në samitin e Bukureshtit, Shqipëria mori ftesën për anëtarësim në NATO.Në këtë periudhë, aleanca drejtohej nga Jap De Hom Shefere, sekretari që zhvilloi dy vizita në Shqipëri.Një vit me vonë, gjatë samitit të Strasburgut, Shqipëria finalizoi synimin e saj dhe flamuri shqiptar u valëvit përkrah 27 flamujve të NATO-s.Sekretari i fundit që vizitoi Shqipërinë ishte Anders Fog Rasmuesen ne 29 prill 2010. Vizita e tij mbahej një vit pas marrjes së detyrës si shefi i NATO-s. Ai vlerësoi kontributin e Shqipërisë ne misionet ndërkombëtare ne Afganistan e Irak.