Первая деревянная церковь во имя Владимирской иконы Божией Матери для солдат Кронштадтского гарнизонного полка была выстроена на Котлине в 1730 - 1735 годах. В 1753 году вместо первоначальной Владимирской Крепостной церкви была устроена новая военно-крепостная церковь. Почти 100 лет этот храм находился в ведении Адмиралтейств-коллегии, а в 1826 году, как и все военно-крепостные храмы, его передали на баланс военного ведомства, хотя среди его прихожан были и флотские чины. В 1764 году церковь была поновлена, но к концу века пришла в столь ветхое состояние, что требовала капитального ремонта или замены новой постройкой. Последнее и было исполнено в 1801 году, когда на ее месте была выстроена точно такая же новая деревянная церковь. К середине XIX века церковь, вмещавшая около 500 человек, оказалась тесной. Кронштадтский военный губернатор вице-адмирал Казакевич обратился по инстанции о целесообразности постройки более вместительной каменной военно-крепостной церкви, на что 21 декабря 1872 года Императором Александром II было дано Высочайшее разрешение.

Существующий каменный храм построен по проекту Д. И. Гримма академиком архитектуры Х. И. Грейфаном в 1875 – 1882 годах на месте прежней деревянной церкви, сгоревшей в 1874 году. Освящение храма было совершено 24 февраля 1880 года. В соборе, кроме главного престола, имелись приделы во имя Божией Матери "Утоли Моя Печали", освященный в 1888 году в нижнем ярусе храма, в крипте и правый придел верхнего храма во имя Блаженного Николая Кочанова, Христа ради юродивого Новгородского (освященный 9 ноября 1908 года епископом Гдовским Кириллом). В 1919 году был освящен придел Казанской Божией Матери. Пятинефная базилика с пятидесятиметровой колокольней вобрала в себя "цитаты" из русской архитектуры XVII века, однако формы и декор трех алтарных апсид и помещенная с западной стороны галерея-паперть выглядят несколько эклектично. Эскизы росписей храма выполнил академик Е. Б. Годун. Храм вмещал до 3000 молящихся. На углу Николаевского проспекта и Владимирской улицы была выстроена каменная часовня, принадлежавшая храму. В 1902 году указом Святейшего Синода храм получил статус собора.

Главной святыней собора была Владимирская икона Божией Матери, написанная 29 мая 1703 года и украшенная серебряной позолоченной ризой с венцом и разноцветными камнями, сооруженной в 1735 году.

Собор был закрыт в 1931 году и частично взорван в 1950-е годы - взрывом были разрушены алтарь, паперть и колокольня, однако храм все же остался стоять. После второго взрыва собора по соседним зданиям пошли трещины. Чтобы сохранить здания, взрывы решили прекратить. В 1960-е годы в соборе планировали разместить то бассейн, то конюшни, то что-то ещё. Около тридцати лет он продолжал пустовать, медленно разрушаясь.

В конце 1990 года собор был возвращен епархии. В полуразрушенном крепостном соборе были произведены консервационные работы, и до 1999 года восстановление святыни велось очень медленно. Богослужения совершались во временной домовой церкви Всех Святых, освященной в 1991 году. С 1999 года службы начали проводиться в здании храма, в нижнем приделе во имя иконы Божией Матери "Утоли Моя Печали".

Одновременно развернулись строительно-реставрационные работы. Были восстановлены разрушенные апсида алтаря, колокольня, паперть. На куполах собора вновь засияли позолоченные кресты.

Сейчас в соборе при участии прихожан продолжаются восстановительные работы в верхнем храме, где уже совершаются службы.

Передана верующим и восстановлена в начале 1990-х годов каменная часовня в ограде собора, на углу Владимирской улицы.