天下已無我祖母說的海參崴。我的子孫，你們還會有東海嗎？

曆史上海參崴曾自唐、遼、金起，這裏已漸見人民活動。元時稱為永明城。清時該地被劃為吉林將軍的領地內。
自17世紀中期，沙俄皇朝伺機東侵，尋求在遠東地區開拓不凍港口。沙俄和清朝曾有著多次領土上的糾紛。雖然在清康熙年間清朝和沙俄簽訂的《尼布楚條約》中明確訂明海參崴屬清朝，但是，清朝中葉國勢日衰，鴉片戰爭後，在1856年清政府和沙俄簽訂不平等的《璦琿條約》，規定包括海參崴的烏蘇裏江以東地區為中俄共管。4年後，在第二次鴉片戰爭中，俄國又與清政府簽訂了不平等的《中俄北京條約》，清政府割讓了烏蘇裏江以東包括庫頁島在內的約40萬平方千米的領土，其中包括海參崴。
隨後其成為沙俄在遠東地區的一個重要的軍事基地，不過由於距離俄國本部太遠，所以該地的發展緩慢。在1891年西伯利亞鐵路開通至此，亦開始有海運路線由其往返日本神戶、長崎及中國上海等地。
1904年至1905年間日俄戰爭中，其曾被日本海軍派遣的分遣艦隊突襲。幸有俄軍巡洋艦隊堅守，使日本海軍轉移目標攻擊遼東半島和大連。
1917年俄國十月革命後，由於蘇聯國內戰爭的混亂情況，反共產黨的勢力在此和俄國遠東地區滲入。當中包括一些外來勢力如英國、美國和日本，日英聯軍在1918年4月借口當地有日資設施被襲，進駐金角灣和此城，1920年遠東濱海地區建立“遠東共和國”，持續至1922年由蘇聯收複。
1930年代開始，此城成為蘇聯流放政治犯的主要地點，而在第二次世界大戰前後，先後囚禁在這裏的包括蘇聯和日本的戰俘。
1954年蘇共第一書記赫魯雪夫到臨此城，並表示其可以跟美國的舊金山相比，亦奠定了其作為蘇聯遠東地區最重點的發展城市之地位。
在2001年7月16日，中國國家主席江澤民與俄羅斯總統普京，在莫斯科克裏姆林宮簽署《中俄睦鄰友好合作條約》，代表中國正式透過官方文件，繼續確認此城及鄰近遠東地區不再為中國的領土。不過，中國民間依然有聲音抗議當年俄國強占海參崴。