Будущему городу предшествовал военный пост на берегу бухты Золотой Рог.

Н.Н. Муравьёв-Амурский назвал пост Владивостоком. В 1860 году на берегу Японского моря поднят государственный флаг Российской империи. В 1871 году во Владивосток переводят пост с резиденцией военного губернатора и главную базу Сибирской военной флотилии. В 1880 году Владивосток официально объявлен городом.

История Владивостока начинается с подписания «Айгунского договора» между Российским и Дайцинским (Китай) государствами от «16 дня 1858 года». Инициатором договора был генерал-губернатор Восточной Сибири Николай Николаевич Муравьёв-Амурский. В итоге Россия обзавелась приморской территорией на Дальнем Востоке Государства.

В 1859 году Н.Н. Муравьёв-Амурский, обходя на корабле берега залива Петра Великого, обратил внимание на хорошо укрытую бухту. Генерал-губернатор предложил назвать её Золотым Рогом и приказал основать на берегах бухты военный пост, который он же, Н.Н. Муравьёв-Амурский, назвал Владивостоком.

Двадцатого июня 1860 года в бухту Золотой Рог прибыл транспорт «Манчжур» под командованием капитан-лейтенанта Алексея Карчалова Шефнера. На берег высадился отряд из 40 человек во главе с прапорщиком Н.В. Комаровым. В вахтенном журнале «Маньчжура» об этом событии 20 июня 1860 года сделана запись: «Сего числа отправлено на берег – один обер-офицер, 2 унитер-офицера и 37 человек рядовых 4-го линейного батальона для занятия поста». В тот же день на месте высадки был поднят государственный флаг Российской империи. На берегах Японского моря возник новый военный пост России Владивосток.

Через месяц после первой высадки в бухту Золотой Рог пришёл винтовой корвет «Гридень» под командованием капитан-лейтенанта Г.Х. Эгершельда. Корвет должен был нести охрану поста Владивосток и обеспечивать гарнизон необходимыми припасами. Штурманская команда по заданию Г.Х. Эгершельда провела промеры бухты. На географической карте, составленной по результатам измерений лейтенантом П.Ф. Чуркиным, впервые появились новые названия: «Гавань и пост Владивосток», «Мыс Чуркина», «Мыс Эгершельда», «Бухта Золотой Рог».

В 1861 году командование постом принял первый официальный командир, лейтенант Е.С. Бурачек, старший офицер клипера «Разбойник». Е.С. Бурачек дожил до 50-летнего юбилея своего города. После смерти прах первого командующего городом был перенесён во Владивосток.

Следующие два года пост быстро строился и расширялся. В 1862 году его переименовали в порт. Росло его население. Двадцать седьмого сентября 1863 года во Владивостоке появился на свет первый собственный гражданин, точнее гражданка. У Евдокии Матвеевны Горелко родилась дочь Надежда.

Осенью 1867 года во Владивостоке побывал известный русский путешественник и географ Н.М. Пржевальский. Вот что он увидел на берегу Золотого Рога: «Под вечер 26 октября добрался я до Владивостока, и в ту же ночь поднялась сильная метель. Владивосток вытянут на протяжении более версты по северному берегу бухты Золотой Рог, обширной и глубокой, со всех сторон обставленной горами и потому чрезвычайно удобной для стоянки судов. Кроме солдатских казарм, офицерского флигеля, механического заведения, различных складов провианта и других запасов, в нём имеется около пятидесяти казённых и частных домов да десятка два глиняных мазанок. Число жителей вместе с войсками простирается до пятисот человек».

Десятого февраля 1871 года правительство решает перевести из Николаевска-на-Амуре во Владивосток порт с морскими учреждениями, резиденцию военного губернатора и главную базу Сибирской военной флотилии. С этого момента  Владивосток растёт уже стремительно. Значительно расширяется строительство административных и жилых зданий, расширяется торговля, начинают работать новые лесопильни и пять кирпичных заводов, мельница, пивоваренный завод. Развитию города способствовал также режим беспошлинной торговли. К 1874 году Светланская, главная улица Владивостока, вытянулась вдоль берега Золотого Рога почти на четыре версты. Улицу назвали так в память о визите во Владивосток фрегата «Светлана». На ней во Владивосток приплыл четвёртый сын императора Александра II князь Алексей Александрович.

В 1875 году военный губернатор Приморской области генерал-майор Симонов разрешил избрать во Владивостоке  городскую думу. Десятого мая 1880 года Владивосток с 7 300 жителями официально был объявлен городом и выделен из состава Приморской области как самостоятельная административная единица. В его территорию вошли полуостров Муравьёв-Амурский и остров Русский. Первым городским головой стал отставной подпоручик Фёдоров. Он правил городом справедливо и умело, за что был награждён четырьмя российскими, японскими и китайскими орденами и многими медалями.

К этому времени открылось регулярное товаро-пассажирское морское сообщение. Девятого марта 1880 года из Одессы во Владивосток отбыл торговый пароход «Москва». Спустя 46 суток пароход благополучно прибыл в бухту Золотой Рог.

В апреле 1883 года увидел свет первый номер газеты «Владивосток». В том же году были организованы перевозки крестьян морем из Одессы во Владивосток. В 1885 году закладывается механический завод, ещё один кирпичный завод, паровая мельница. В 1893 году открылось железнодорожное движение между Владивостоком и Никольским (Уссурийск), а в 1897 году поезда пошли до Хабаровска.

В мае 1891 года во Владивосток после полугодового кругосветного морского путешествия пришёл крейсер «Память Азова». На его борту находился великий князь, наследник престола, будущий последний император России Николай II. Прибыв во Владивосток, он участвовал в закладках восточного участка Транссибирской магистрали, железнодорожного вокзала, сухого дока для ремонта судов Тихоокеанской эскадры, а также памятника адмиралу Г.И. Невельскому. В честь пребывания наследника российского престола во Владивостоке на улице Петра Великого была построена Триумфальная арка, замечательное архитектурное сооружение того времени. Снесли арку в 1927 году.

В 1899 году во Владивостоке был основан Восточный институт, первое высшее учебное заведение на Дальнем Востоке. В 1907 году парадный вход в здание был фланкирован двумя привезёнными из Манчжурии скульптурами фантастических львов «ши-цзы», целиком высеченных из гранита. В этом же году сходные изваяния львов были отправлены в Петербург. Они и поныне стоят у пристани на Петровской набережной.

В 1900 году Владимир Клавдиевич Арсеньев, тогда молодой офицер, добился перевода для прохождения службы во Владивостоке. За 30 лет жизни на Дальнем Востоке этот знаменитый исследователь, писатель и географ совершил более 20 экспедиций, написал свыше 80 книг и статей.

К началу XX века крохотный военно-морской пост превратился в крупнейший порт и военно-морскую базу России на Дальнем Востоке.

Русско-японская война лишь краешком задела город: обстрел, частичная эвакуация. Основная же тяжесть войны была южнее, в Корее, у стен Порт-Артура, в Манчжурии. В то же время город начали интенсивно укреплять. Владивостокская крепость, почти законченная к 1915 году, считалась лучшей из всех приморских крепостей мира.