Строительство этой церкви епископ Евсевий задумал вскоре после прибытия во Владивосток в 1899 году.

Из-за того , что ему негде было постоянно жить, владыка решил построить загородную дачу для постоянного жительства. Для нее был выделен участок в 15 десятин в живописном месте недалеко от железнодорожной станции Седанка. К строительству приступили в 1900 году и закончили его в 1901 году. Получилось своеобразное архиерейское подворье, которое включало в себя каменный двухэтажный дом, церковь с колокольней, три деревянных флигеля для свиты и прислуги и разнообразные служебные постройки. Здесь же помещалась церковно-приходская школа для обучения проживающих на иждивении его преосвященства детей-сирот. Домовый храм был освящен во имя священномученика Евсевия, епископа Самосатского.

30 августа 1910 года в день памяти святого благоверного князя Александра Невского недалеко от архиерейского дома была произведена закладка каменного храма-часовни. Храм был заложен над могилой владивостокского жителя, бывшего консула и инициатора учреждения русской концессии в Ханькоу, Александра Степановича Ваховича. 9 февраля 1911 года храм-памятник был освящен архиепископом Евсевием во имя святого благоверного князя Александра Невского.

В 1914 году при архиерейском доме была открыта церковно-учительская семинария для девочек из семей духовного звания. С 1915 года комплекс вокруг Свято-Евсевиевской церкви стал называться архирейским подворьем, ставшим духовным центром Владивостока.