Wilno dość późno zostało opasane murami obronnymi. Przyczyną tego były rozpoczynające się wielkie wojny moskiewskie, ekspansja Moskwy na Zachód przeciwko Litwie oraz najazdy czambułów tatarskich. Toteż na początku XV wieku mieszczanie wileńscy zwrócili się do wielkiego księcia i króla Aleksandra I (1461-1506) o przywilej wybudowania fortyfikacji.
W tym czasie, po śmierci Kazimierza Jagiellończyka, od 1492 roku władał Wielkim Księstwem Litewskim Aleksander Jagiellończyk. Znał język litewski, był zarazem ostatnim wielkim księciem litewskim, który posiadał tę umiejętność. Książę dbał o rozwój stołecznego Wilna, jak i o sprawy ważne dla całego państwa.
Będąc już królem polskim i równocześnie wielkim księciem litewskim i dbając o bezpieczeństwo Wilna, a także przychylając się do prośby mieszczan wileńskich, Aleksander 6 września 1503 wydał przywilej zbudowania murów obronnych, ponieważ mieszczanie prosili władcę:
„Miesto wilenskoje niezatworennoje i jestliby na służbu naszu pojechali, tohdy jeho Boże wschowaj sztoby tomu miestu naszemu szkody ot pahnastwa…”.
Mieszczanie wileńscy prosili króla o zwolnienie ich od służby wojskowej w obawie, aby w czasie ich nieobecności miasto nie poniosło szkody od pogan.
Z chwilą wydania wspomnianego przywileju, z Moskwą był zawarty rozejm 6-letni, z tej więc strony nie groziło bezpośrednie niebezpieczeństwo, zresztą wojny moskiewskie nie sięgały tak daleko w głąb kraju. Natomiast z Tatarami wówczas walka wrzała prawie nieustanna. Zagony Tatarów coraz zuchwalej posuwały się ku północy Litwy, podobno potrafiły posuwać się 30 mil w ciągu doby. Mieszczanie wileńscy obawiali się, że hordy tatarskie mogą podejść pod Wilno.
A gród nad Wilią w XV wieku był miastem drewnianym, swobodnie rozrzuconym.
W 1503 roku wielki książę Aleksander rozkazał mieszkańcom Wilna iść na wyprawę, zapewne przeciwko Tatarom, mieszczanie zaś, bojąc się zostawić bezbronne miasto, prosili księcia o zwolnienie od wyprawy, a w zamian obiecali wybudowanie murów obronnych wokół Wilna. Wielkiemu księciu wydała się ta prośba słuszna.
„Przywilej wielkoksiążęcy — pisze Leonid Żytkowicz — polecał zbudować, prócz muru obwodowego, pięć bram:
1) za dworem starościńskim ku Wilii — później nazywana Wilijską, potem Wileńską, 2) koło Matki Boskiej ku Trokom — Trocką, 3) koło św. Trójcy — Miednicką, później zwaną Ostrą od przedmieścia Ostry Koniec, 4) koło cerkwi Spaskiej nad Wilenką i 5) łączącą gród książęcy z miastem.
Jak stwierdzają badacze dziejów Wilna, pierwotny plan jednak uległ zmianie, możliwe, że pod wpływem ówczesnego biskupa, Wojciecha Tabora (1492-1507), któremu prawdopodobnie zależało, by i jego juryzdyka została objęta obwarowaniem, toteż w wykonaniu fortyfikacje miejskie nie tworzyły odrębnego obwodu zamkniętego, lecz oparły się o mury zamkowe z jednej strony, a z drugiej urywały się przy kościele św. Franciszka i Bernardyna (Bernardynów). Nie wiadomo, kim był architekt wznoszący mury, nieznana też jest dokładna data budowy. Maciej Miechowita (właśc. Maciej Karpiga, 1457-1523), a za nim inni kronikarze podają rozpoczęcie na rok 1506. Badacz problemu, Leonid Żytkowicz, uważa, że mury wileńskie powstały między rokiem 1503 a 1522. Z tego wynika, że budowane były 19 lat.
Leonid Żytkowicz ustalił, że „mur zaczynał się niedaleko dzwonnicy katedralnej, od której oddzielało go koryto Wilenki, bo w jeszcze w XIV wieku rzeka ta miała inny bieg niż obecnie; biegł ulicą Bonifraterską (L. Stuokos-Gucevičiaus), lewą stroną Ludwisarskiej (Liejyklos) — obok wybudowanego klasztoru św. Ignacego, przecinał w poprzek ulicę Wileńską (Vilniaus) i, nie dochodząc do ulicy Zawalnej (Pylimo), załamywał się w lewo i ciągnął łukowato wzdłuż niej, po czym skręcał na Bazyliańską (Bazilijonų), omijał klasztor św. Ducha, przecinał ulicę Subocz (Subačiaus) u wylotu ulicy Bakszta (Bokšto), następnie po pochyłości wzgórza opadł ku Wilence, której brzegiem dochodził do kościoła Bernardynów i tu się kończył. Linia w ten sposób wytknięta nie obejmowała całego miasta, lecz znaczne jego części pozostawiała za murami, jako przedmieścia, o czym świadczą zgodnie kronika Miechowity i plan Brauna”.
W całej rozciągłości, mającej 2,9 km, mur posiadał następujące bramy:
1) Mokrą, czyli św. Magdaleny, w pobliżu nieistniejącego dziś kościoła tej nazwy, obok dzwonnicy katedralnej. 2) Tatarską, o której wspomina się po raz pierwszy w 1598. Następne bramy: 3) Wilijska, później Wileńska, 4) Trocka, 5) Ostra i 6) Spaska wymienione są w przywileju z 1503. Dwie następne bramy: 7) Rudnicka, znajdowała się u wylotu ulicy Rudnickiej (Rudininkų) na Zawalną (Pylimo) i 8) Subocz — przy zbiegu ulicy Subocz (Subačiaus) i Bakszta (Bokšto), jak i wyżej wymienione powstały przed 1522 rokiem; 9) Bernardyńska brama wymieniona została po raz pierwszy w 1593 roku.
Żytkowicz dowodzi, że „bramy Mokra, Tatarska i Bernardyńska nie posiadały charakteru warownego, natomiast wzmacniały mury wileńskie baszty:
1) okrągła baszta — między bramami Ostrą i Rudnicką, mniej więcej u wylotu dzisiejszej ulicy Końskiej (Arklių) na Bazyliańską (Bazilijonų), 2) baszta, nieco na północ od bramy Subocz, w tym miejscu ok. 1640 roku zbudowany został barbakan (bastion) przez inżyniera Friedricha Getkanta (?-1666), składał się on z wieży w murze miasta, podziemnych portali i korytarzy, które łączyły 48-metrowy długi tunel. 3) baszta, bez ustalonej nazwy, znajdowała się nad Wilenką, koło nieistniejącej obecnie cerkwi Spasa (Zbawiciela). Wszystkie te baszty zaznaczone są u Getkanta i zapewne powstały przed rokiem 1648”.
Barbakan zburzyli Moskwianie podczas wojny moskiewskiej w 1655 roku. W końcu XVIII w. urządzono w tym miejscu wysypisko miejskie. Podczas pierwszej wojny światowej, w 1915-1916, Niemcy umocowali sklepienia, zabetonowali, wykonali wentylację. Podczas drugiej wojny światowej znajdował się tu niemiecki magazyn amunicji, a w czasach sowieckich urządzono magazyn warzyw. Dopiero w latach 1985-1986 barbakan wyremontowano i w 1987 r. otwarto muzeum. Od strony bramy Ostrej posiadało Wilno rodzaj fosy, utworzonej przez strumienie zlewające się następnie w rzeczkę Koczerhę, wpadającą do Wilenki obok baszty Mokrej. Nie wiadomo jednak, kto te mury obronne w Wilnie budował. Ogólnie linia murów miejskich liczyła więc 2,9 km. Na tej przestrzeni rozwijało się miasto XV-XVI wieków.
Według jednej z legend wileńskich, największą zasługę w budowie murów obronnych miał biskup Wojciech Tabor. Znana legenda głosi:
„Gród Giedyminowy, opasany tylko drewnianym parkanem, już nieraz od wrogów ucierpiał. Pustoszyli go Krzyżacy, Tatarzy, wojska carów moskiewskich i sami książęta litewscy w czasie walk między sobą. Zamek królewski na Turzej Górze, opasany zewsząd Wilią i Wilenką, był prawie niezdobyty, ale miasto, niemające murów, stało bezbronne, tym bardziej że mieszkańcy nie zawsze byli zdolni skutecznie bronić swych siedzib.
Biskup Tabor, bolejąc nad klęskami, jakich Wilno tylekroć doznawało, postanowił zaradzić złu, zwłaszcza że w tym czasie hordy tatarskie pustoszyły Litwę i Wilnu groziło niebezpieczeństwo. Przedstawił tedy królowi i magistratowi konieczność obwarowania miasta.
Wyjednał u króla rozkaz, aby każdy obywatel dzielnicę, w której ma posiadłość, murem obwiódł, za co na rok jeden był wolny od służby wojskowej i płacenia podatku. Gdy w roku następnym Tatarzy, spustoszywszy okolice Mińska i Słucka, zdawali się zmierzać ku Wilnu, przerażeni mieszkańcy szybko i gorliwie wzięli się do roboty pod osobistym dozorem biskupa. Sędziwy pasterz na czele uroczystej procesji, w asystencji całego duchowieństwa obszedł miasto, poświęcając i odprawiając modły w miejscach, gdzie miały stanąć bramy.
Dla wszystkich robotników zastawiono kosztem biskupa stoły z jadłem, po czym przystąpiono do pracy. Kilka tysięcy ludzi stanęło na wyznaczonych miejscach. Nie tylko mieszczanie, kobiety i dzieci, ale również szlachta, magnaci i księża nosili materiał budowlany. Każdy poczuwał się do obowiązku i pragnął bodaj choć jedną cegiełką przyczynić się do dzieła, toteż mury rosły z zadziwiającą szybkością.
Ale skarb magistratu nie był na tyle zasobny, żeby tak kosztowne dzieło do końca mógł doprowadzić, co widząc, biskup Tabor nie pożałował własnej szkatuły, oddając na prowadzenie budowy całkowity dochód z kilku majętności, dostarczając z własnych dóbr robotnika i pożywienie dla pracujących. Olbrzymie musiały to być wydatki, ale świętobliwy pasterz, powodowany skromnością, gdy mur stanął, spalił wszystkie swe księgi rachunkowe, aby nikt nigdy nie dowiedział się, ile na to grosza wyłożył.
I znowu uroczysta procesja z wolna się posuwała wzdłuż nowo wzniesionych murów. Prowadził ją biskup Tabor pontyfikalnie przybrany w asystencji kapituły. Za nim szedł król Zygmunt w otoczeniu senatorów i magnatów litewskich. W procesji wzięły udział wszystkie duchowne zakony wileńskie, cechy z chorągwiami, wojsko i niezliczone tłumy odświętnie przybranego ludu. Domy upiększono kwieciem, z okien zwieszały się drogie kobierce i makaty. Dzwony ze wszystkich kościołów i uroczyste śpiewy wypełniały powietrze. Muzyka grała, strzelano z dział i rusznic.
Od czasu do czasu wstrząsnął powietrzem huk wielkiego działa Witoldowego, ustawionego około cerkwi Pationki, czyli Piatnickiej przy ulicy Wielkiej. Przygarbiony wiekiem biskup miał na twarzy wyraz szczęścia i radości. Gdy stawał przed każdą z pięciu bram, padał na twarz i ze łzami dziękował Bogu Najwyższemu, iż mu dzieła szczęśliwie dokonać pozwolił. Z pięciu bram dotąd przetrwała jedna tylko i zasłynęła w całym świecie chrześcijańskim. Jest to brama Miednicka, czyli Ostra z cudownym obrazem Najświętszej Panny. Pracowity żywot biskupa zbliżał się ku końcowi. Pasterz spokojnie oczekiwał śmierci i żegnał się z otaczającymi go przyjaciółmi, księżmi i kapitułą, gdy do komnaty weszło poselstwo od króla i miasta na czele z burmistrzem.
Na widok umierającego dobrodzieja wszyscy padli na kolana, a burmistrz drżącymi ze wzruszenia słowy dziękował pasterzowi w imieniu króla i miasta za wszystkie dobrodziejstwa, jakie Wilnu świadczył, po czym prosił, by biskup pozwolił ku wiecznej o nim pamiątce wznieść jego pomnik na murach, którymi dzięki jego staraniom miasto zostało opasane. Nie zgodził się na wielki w swej skromności starzec i dziękując, za dobre chęci rzekł:
— Najlepszym dla mnie pomnikiem będzie mur, który, aby był trwałym, wy i wasi potomkowie brońcie go przed wrogiem i podtrzymujcie, by się w gruzy nie rozpadł. Tejże nocy żałobne dzwony z wież wszystkich kościołów wileńskich obwieściły miastu, że biskup Wojciech Tabor umarł”.
Tyle legenda, a fakty historyczne są następujące: historyk Leonid Żytkowicz przed II wojną światową ustalił, że mury obronne Wilna powstały między rokiem 1503 a 1522. Po śmierci Aleksandra, Zygmunt zwany Starym, został wyniesiony na tron wielkoksiążęcy 20 października 1506 roku, natomiast biskup Wojciech Tabor zmarł 27 marca 1507 roku.