Своё название башня получила от Владимирской надвратнойьцеркви 1311 года, выстроенной по указанию новгородского архиепископа Давида, через башню проходила дорога в Неревский конец Софийской стороны Новгорода. До постройки этой башни путь из Детинца в Неревский конец проходил через Фёдоровскую башню. По результатам проведённых археологических раскопок под руководством М.Х. Алешковского в 1957 году, было выявлено что башня построена на более ранних фундаментах. В 1461 году по указанию новгородского архиепископа Ионы Владимирская привратная церковь была полностью перестроена, а также к ней была пристроена трапезная, вероятно тогда же была перестроена и башня. В XVI века на внешнем фасаде башни был написан образ Николая Чудотворца, фреска сохранилась до наших дней, откуда происходит другое название башни, Никольская. В XVI веке и в 1660-ых годах бойницы башни переделывали, а в конце XVIII века башня была отремонтирована, пристроенная трапезная Владимирской привратной церкви была разобрана, но была пристроена двухэтажная Никольская часовня с проездом к Волхову из Архиерейского сада Детинца.
Во время Великой Отечественной войны башня получила значительные повреждения. В 1959—1961 годах по проекту А.В. Воробьёва и Н. С. Кривулиной башня была восстановлена в формах XV века, двухэтажная Никольская часовня была разобрана, но были восстановлены утраченные в XVIII веке этажи башни, а также были завершены работы по укреплению фундаментов башни начатые в 1930-ых годах, которые предотвратили оседание башни.
