Хайшеньвэй – так по-китайски называется Владивосток, что переводится как «залив трепанга» (см. Трепанг) или «бухта голубого трепанга».
В древности данная территория входила в состав государства Бохай (698—926 гг.), начиная с X века она принадлежала киданям, а затем чжурчжэням. В начале XIII века на территории современного Приморья существовало несколько городов чжурчжэньского государства Восточное Ся. Все они были разрушены монголами в результате нападения 1233 года, после чего территория пришла в запустение. Позднее из-за споров между маньчжурами и ханьцами южное Приморье обезлюдело и практически не упоминалось в источниках вплоть до XIX века.
20 июня (2 июля по новому стилю) 1860 года транспорт Сибирской флотилии «Манджур» под командованием капитан-лейтенанта Алексея Карловича Шефнера доставил в Золотой Рог воинское подразделение для основания военного поста, который теперь уже официально получил название Владивосток.
Интересно, что в период с 1854 по 1856 год англичане на судах «Винчестер» и «Барракуда» из состава англо-французской эскадры, в ходе Крымской войны искавшей российский флот по всему миру, заходили в бухту Золотой Рог, где сегодня расположен Владивосток, и назвали увиденную ими гавань «Порт Мэй» (Port May), что, кстати, неожиданно рифмуется с «Хайшеньвэем» (а также с «внешним Дунбэем», как зовут всё нынешнее Приморье китайцы). Англичане и французы дали свои названия и другим географическим объектам в районе нынешнего Владивостока: залив королевы Виктории (ныне – Петра Великого), залив императора Наполеона (нынешний Уссурийский), полуостров принца Альберта (в русской версии – Муравьёва-Амурского). До основания Владивостока тогда оставалось ещё несколько лет, в течение которых были заключены договоры с Китаем (см. Муравьёв-Амурский, Николай), сделавшие возможным освоение территорий нынешнего Приморья Россией. На тот момент история вполне могла пойти совсем по другому руслу. Поговаривают, что англичане планировали превратить Порт Мэй в «Северный Гонконг».
Французские моряки бывали здесь ещё раньше. Знаменитый Лаперуз прошёл вдоль приморских берегов в 1787 году, оставив сохранившееся до наших дней наименование «Терней» (так называются посёлок на севере Приморья, где рубят лес и нерестится лосось, и целый Тернейский район) – в честь французского мореплавателя адмирала Шарля д’Арсака де Тернея. Считается, что именно из-за ошибки Лаперуза Сахалин долгое время считался полуостровом, что впоследствии пришлось опровергать Геннадию Невельскому.