A cidade fundouse en 1783 ao anexionar Rusia a península de Crimea, pola súa posición estratéxica converteuse nunha importante base naval e máis tarde nun porto comercial. En 1797 a cidade pasou a se denominar Akhtiar, nome dun asentamento tártaro nas súas proximidades, en 1826 a cidade recuperou o seu nome actual. Sebastopol foi teatro de operacións en diferentes conflitos bélicos, permaneceu asediada durante once meses (1854-1855) durante a Guerra de Crimea, foi sede dende 1918 ata 1920 do cuartel xeral do Exército Branco baixo o mando de Piotr Nikolaievich Wrangel e na segunda guerra mundial sufriu o asedio alemán durante 250 días (1941-1942) que aniquilou a gran parte da poboación. Durante a época da Unión Soviética Sebastopol foi unha cidade pechada, dependente directamente das autoridades centrais.
