Храм строили с 1875 по 1879 годы по проекту Д. И. Гримма на государственные средства, общая сумма составила 201687 рублей. Ранее в этом месте располагалась деревянная церковь 1753 года постройки, которая сгорела в пожаре. Фасады каменного храма были задуманы как традиционная церковь в русском стиле архитектуры 17 века, однако внутренняя планировка помещений копирует базилики раннехристианских церквей и по планировке схожа с внутренней планировкой церкви Сант-Аполлинаре-Нуово в Равене. В период Великой Отечественной войны здание сильно пострадало и позже его пытались снести.
Первый деревянный храм Владимирской иконы Божией Матери для Кронштадтского гарнизонного полка был построен в 1730-1735 годах. В 1753 году вместо прежнего храма на пожертвования на углу Владимирской и Михайловской улиц был устроен новый.
К 1798 году церковь находилась уже в ветхом состоянии и в 1801 году она была сломана. На том же месте была возведена такая же деревянная церковь, рассчитанная на 500 человек. Храм строился на средства, собранные Кронштадтским гарнизонным полком и другими командами сухопутного ведомства. Одновременно с востока, за алтарём церкви была выстроена и часовня.
В 1825 году для причта Владимирской церкви был построен деревянный двухэтажный дом.
В 1836 году храм, до этого состоявший в ведении Адмиралтейств-коллегии, в связи с реорганизацией последней, был передан на баланс военного ведомства.
В ночь на 10 (22) июля 1826 года в пожаре погибла часовня, а в 1874 году, в ночь на 21 октября (2 ноября), сгорел деревянный храм. На его месте была построена временная деревянная церковь, впоследствии, в связи с окончанием строительства каменного храма, она была разобрана. Материал разобранного храма был использован при строительства Мариинского приюта для вдов и сирот военно-морского духовенства.
В середине 19 века деревянная церковь оказалась малой для того, чтобы удовлетворять нуждам крепостного гарнизона, состоявшего из 4500 нижних чинов. Кронштадтский военный губернатор вице-адмирал Казакевич подал прошение о строительстве каменного собора, и 21 декабря 1872 (2 января 1873) получил высочайшее разрешение. Для новой церкви инженерное ведомство приобрело у купца Ильина за 7050 рублей серебром место, находившиеся рядом с церковным.
Торжественная закладка нового храма состоялась 8 мая 1875 года. Храм строился по проекту Д. И. Гримма, руководил работами академик архитектуры Х. И. Грейфан. Храм был рассчитан на 3000 человек. Основной объем здания был возведен к 1879 году, внутренняя и внешняя отделка завершена в 1882 году. Роспись церкви осуществлялась по эскизам Е. В. Годуна. Все строительные работы велись на государственные средства, их общая сумма составила 201687 рублей.
Освящение церкви главным священником армии и флота протоиереем Петром Покровским состоялось 24 февраля (7 марта) 1880 года.
- 25 октября (6 ноября) 1888 года был освящён нижний придел во имя иконы Божией Матери «Утоли моя печали».
- 9 (22) ноября 1908 года епископом Гдовским Кириллом был освящён правый придел верхнего храма во имя блаженного Николая Кочанова, Христа ради юродивого Новгородского.
- Придел Казанской иконы Божией Матери был освящён в 1919 году.
Фасады храма задуманы как традиционная церковь в русском стиле архитектуры 17 века, однако внутренняя планировка помещений копирует базилики ранехристианских церквей и по планировке схожа с внутренней планировкой церкви Сант-Аполлинаре-Нуово построенной в 5 веке в Равене, для сходства с римским стилем потолок выполнен также с использование кессонов. Высота колокольни храма составляет 50 метров.
Приказом по Военному ведомству от 7 (20) сентября 1902 года (№335) гарнизонная церковь получила статус собора.
16 февраля 1931 года собор был закрыт и переоборудован под склад.
В период Великой Отечественной войны бывшее церковное здание сильно пострадало и впоследствии было принято решение его снести. В 1950-х годах здание трижды пытались взорвать, но работы эти было решено прекратить, поскольку они вызвали появление трещин в соседних домах. В результате взрывных работ были разрушены алтарь, паперть и колокольня. Существовали проекты размещения здесь бассейна или конюшен, но они не были реализованы, бывшее здание церкви не использовалось и пустовало.
В 1990 году здание передали Русской православной церкви. Были проведены консервационные работы, а службы проводились во временной церкви Всех святых. В 1999 году начались службы в нижнем храме иконы Божией Матери «Утоли моя печали».
В 2000—2001 годах была перебрана кирпичная кладка, произведена расчистка и штукатурка фасадов, воссозданы главки куполов из оцинкованной стали. Позже были воссозданы орнаменты на потолке и стенах храма, отреставрированы семь фигурных композиций, храму был возвращен его первоначальный облик.
В своё время главной святыней собора был список Владимирской иконы Божией Матери, написанный 29 мая (9 июня) 1703 года по приказу Петра I специально для Кронштадта. Образ был исполнен маслом на металле и украшен позолоченной медью. В 1735 году для иконы были устроены бронзовый киот и сребро-вызолоченная риза с венцом и разноцветными камнями. На иконе была надпись: «Сей образ написан ЗCI года мая 29 дня, оклад сделан 1735 года февраля 20-го дня». Образ располагался по правую сторону Царских врат. В 1931 году икона была изъята, её судьба неизвестна. В церкви также хранились знамёна различных воинских частей.
Стоит также отметить, что на углу проспекта Ленина (Николаевского проспекта) и Владимирской улицы в 1870 году на средства новгородского купца Василия Васильевича Епишкина была выстроена каменная часовня, которая действует и в настоящее время. Рядом с часовней находилась могила протоиерея Василия Салтыкова, над которой в июле 1898 года был установлен памятник из серого мрамора, обнесённый железной оградой.