Мысль о строительстве этой церкви родилась тогда, когда поступили известия о больших людских потерях со стороны России в русско-японской войне.

Начальник русской духовной миссии в Корее архимандрит Павел предложил для увековечения памяти павших воинов построить во Владивостоке храм-памятник. Причем этот храм архитектурно должен был соединить в себе церковь и школу, в которой могли бы обучаться дети простых людей. Строительство храма началось в мае 1907 года, а закончено в декабре того же года. Храм построили на добровольные пожертвования, главным образом военных лиц.

При церкви имелись училище с ремесленным отделением, библиотека, квартиры учителя и законоучителя. 9 декабря 1907 года церковь-школа была торжественно освящена архиепископом Евсевием. Престол храма был освящен во имя иконы Божией Матери "Всех скорбящих радость". Над главным входом в двухэтажное здание была сделана надпись: "Памяти убиенных русских воинов 1904-1905 годов".

Регулярные занятия в церкви-школе начались в 1908 году. В 1909 году в школе обучалось 77 детей из рабочей и матросской слободок. В 1913 году городская начальная школа № 6 "Памяти убиенных воинов" из здания церкви-школы была переведена в городской дом. В здании церкви-школы с 1913 года действовала школа духовной миссии и упрощенное катехизаторское училище с одногодичным курсом.