Успенский кафедральный собор - главный православный храм города и епархии - начинался со скромной деревянной воинской церкви Успения Пресвятой Богородицы поста Владивосток, построенной в 1862 году.

Ее строительство благословил архиепископ Камчатский, Курильский и Благовещенский Иннокентий (Вениаминов). Он же подписал и направил в церковь антиминс для совершения на нем Божественной литургии. Со стороны гражданских властей руководил строительством Успенской церкви начальник поста Владивосток лейтенант Евгений Степанович Бурачек. 1 апреля 1862 года церковь иеромонах Филарет, судовой священник корвета "Гридень", совершил чин освящения Успенской церкви и стал первым служившим в ней настоятелем. Размеры храма были невелики: в длину 19 м. В ширину 8, 5 м. Имеля лишь один колокол весом в 1 пуд. Через три года после постройки церкви многие бревна в ней начали гнить, что объясянялось близостью к бухте и действием морских туманов. Поэтому, с целью предохранения церкви от дальнейшей порчи, было решено перенести ее на 70 метров выше к северу. Эти работы были соершены под руководством нового настоятеля церкви иеромонаха Валериана, капитана Буяковича и поручика Каблукова. На новом месте Успенская церковь вновь освящена 19 марта 1866 года. На этом месте церковь простояла до 1890 года, когда она была разобрана и перенесена в казармы сухопутных войск.

В 70-х годах стал обсуждаться вопрос о строительстве во Владивостоке новой каменной церкви. К сбору средств на ее строительство подключились военный губернатор и генерал-губернатор Восточной Сибири. Закладка нового Успенского храма состоялась 14 августа 1876 года. Фундамент был заложен рядом со тарой церковью. Но работы велись долго из-за постоянной нехватки средств. Освящение Успенского кафедрального собора состоялось 6 декабря 1899 года. Чин освящения совершил епископ Камчатский, Курильский и Благовещенский Гурий. Архитектурно собор был исполнен в русском кресто-купольном стиле. Его высота равнялась 35 метрам. Он вмещал около 1000 молящихся. Кроме праздника Успения Пресвятой Богородицы, собор отмечал и еще один престольный праздник, поскольку в нем был придел, освященный во имя святого равноапостольного Князя Владимира, просветителя русского народа. Газета "Дальний Восток" от 13 июля 1908 г. писала: "Во Владивостокском кафедральном соборе 14 июля будет совершено в 6 часов вечера всенощное бдение, а 15 июля в 9 часов утра торжественная литургия по случаю престольного праздника в соборном приделе, освященном во имя Святого Равноапостольного Князя Владимира". С 1899 года Успенский собор получил статус Кафедрального собора.

На соборном участке с разрешения властей в 1908 году началось строительство дома "для помещения в нем соборной библиотеки, канцелярии, крещальни, лавочки с предметами религиозного чествования и церковной утвари и для церковных сторожей. Необходимость его постройки видна из того, что до сих пор библиотека, канцелярия, архив, утварь, с каждым годом множащиеся, помещались в самом соборе, что во всех отношениях неудобно". ("Дальний Восток", 31 октября 1908 г.).

Хотя Успенский собор был большим, в большие праздники не все желающие могли войти внутрь. Поэтому уже в 1899 году был образован комитет по строительству нового кафедрального собора. Городская управа выделила участок земли на Суйфунской площади (ныне здесь расположен сквер имени Суханова, расположенный рядом с телецентром). Новый собор предполагалось назвать именем святителя Николая и по размерам он должен был вмещать 3000 человек.