Pirms 1860. gada Pekinas konvencijas parakstīšanas tagadējās pilsētas vietā atradās mandžūru apmetne ar nosaukumu Haišenvaja (ķīniešu: 海参崴). Pēc nokļūšanas Krievijas Impērijas pakļautībā to pārdēvēja par Vladivostoku (krievu: Владивосток — "Austrumu valdnieku") pēc līdzības ar Ziemeļkaukāza cietoksni Vladikaukāzu - "Kaukāza valdnieku". 1871. gadā tā Nikolajevas vietā kļuva par galveno Krievijas Impērijas Klusā okeāna tirdzniecības ostu. Pilsētas nozīme pieauga, kad 1903. gadā Vladisvostoka kļuva par Transsibīrijas dzelzceļa galapunktu. Krievijas pilsoņu kara laikā Vladivostoka bija japāņu intervences centrs un Pieamūras pagaidu valdības mītne. Sarkanā armijaJeronima Uboreviča vadībā 1922. gada 25. oktobrī ieņēma Vladivostoku, un beidza Tālo Austrumu Republikas pastāvēšanu, ko uzskata par Krievijas pilsoņu kara beigām.
Luterāņu garīgo aprūpi 1909. gadā būvētajā luterāņu Svētā Pāvila baznīcā no 1880. līdz 1912. gadam veica Kārlis Augusts Rumpēters (1849-1912; apglabāts Vladivostokas Jūras kapos (Морское кладбище)).[1][2][3] Viņa, kā arī vēlāko Vladivostokas luterāņu mācītāju aprūpē atradās arī Sibīrijas un Tālo Austrumu latviešu kolonijas, ieskaitot Lejas Bulānu un Amūras Baltiju.[4][5]