Вторым по размерам приходским храмом Владивостока была Покровская церковь. Ее строительство началось после приезда во Владивосток епископа Евсевия.

3 мая 1900 года была совершена закладка фундамента храма, а освящение состоялось 29 сентября 1902 года самим епархиальным архиереем. Сооруженный храм был довольно обширен - вмещал до 1000 прихожан. В храм вели три двери с широкими каменными крыльцами (с севера, запада и юга). Над средней частью храма поднимался высокий купол. Церковь имела много окон, из-за чего в ней было много света. Этот храм расположился на окраине городского кладбища, поэтому часто его называли кладбищенским.

Согласно с указом Владивостокской духовной консистории (№ 2793, 1902г.) прихожанами этой церкви были определены жители улиц: Фонтанной (северная сторона), Пологой, Комаровской, Последней (сейчас ул. Уткинская), Корейской слободки и Первой Речки. При храме была построена кирпичная школа для детей корейцев. Известно, что ее настоятелем одно время был протоиерей Василий Попов, бывший также редактором "Владивостокских епархиальных ведомостей".