Строительство храма планировалось с 1825, подготовка к работам начата в 1848, закладка состоялась в 1854. Из-за Крымской войны работы остановлены, возобновлены в 1860-х по новому проекту. Четырехстолпный однокупольный храм с пониженными угловыми компартиментами, перекрытыми полукуполами, выстроен в неовизантийском стиле. Стены сложены из известняка, декор из мрамора и лабрадорита. Нижний Никольский храм освящен в 1881, верхний Князь-Владимирский в 1888. Закрыт в 1932, в 1941-1942 пострадал от обстрелов. Реставрируется с 1966, в 1973 передан музею. С 1991 в совместном пользовании общины верующих и музея.
Собор является храмом-памятником героической обороне Севастополя в 1854-1855. В цокольном этаже собора похоронены погибшие во время обороны адмиралы В. А. Корнилов, В. И. Истомин и П. С. Нахимов, а также ряд других командующих Черноморским флотом и участников обороны. В верхнем этаже размещены мемориальные доски с именами погибших в дни обороны офицеров флота.
см. сайт