Sākot no 7. gadsimta p.m.ē. Senās Grieķijas kolonisti Krimas pussalas dienvidu krastā pie tagadējās Sevastopoles izveidoja Hersonesas koloniju. 63. gadā p.m.ē. Krima kļuva atkarīga no Romas impērijas. Lai arī 7. gadsimta beigās Krimu iekaroja hazāri, Hersonesas pilsēta palika Bizantijas pakļautībā. 988. gadā Kijivas rūsu lielkņazs Vladimirs Svjatoslavičs ieņēma Hersonēsu (krievu: Корсунь) un pieprasīja par sievu Bizantijas princesi Annu, pretējā gadījumā draudot uzbrukt Konstantinopolei. Bizantieši piekrita, ja kņazs Vladimirs kristītos, kas arī tika izdarīts Hersonēsas baznīcā, ko uzskata par sākumu Kijivas Krievzemes pārejai kristīgajā ticībā. Kad 1239. gadā Batuhans iekaroja Krimas ziemeļu daļu, tagadējās Sevastopoles teritorija ietilpa kristiešu Teodoras valsts sastāvā. 1475. gadā to pakļāva Osmaņu impērijas vasaļvalsts Krimas haniste. 1774. gadā Krievijas Impērija piespieda Osmaņu impēriju atteikties no Krimas hanistes, kas nokļuva Krievijas Impērijas atkarībā. 1783. gada 19. aprīlī Krievijas Impērija anektēja Krimu un inkorporēja to impērijas sastāvā. Krimas tatāru ostu Ahtjaru (Aqyar — "Baltais krasts") pārdēvēja par Sevastopoli (no grieķu: Σεβαστός πόλη — "Godājamā pilsēta"). Pēc ķeizarienes Katrīnas II nāves viņas dēls Pāvils I lika cietoksnim atgriezt seno nosaukumu, bet ķeizars Nikolajs I to 1826. gadā atkal lika to pārdēvēt par Sevastopoli.
1853.—1856. gadā Sevastopoles apkārtnē notika galvenās Krimas kara kaujas, pēc kurām krievu armija bija spiesta atstāt pilsētu un nogremdēt kara kuģus, lai tie nenokļūtu pretinieku rokās. Krievijas pilsoņu kara sākumā Krimā nodibināja Taurijas padomju republiku, 1918.-1920. gadā vara atradās vācu okupācijas iestāžu, vēlāk Deņikina un Vrangeļa valdību rokās. Pēc uzvaras Perekopa kaujā 1920. gada novembrī Sarkanā armija iekaroja Sevastopoli. No 1921. gada 18. oktobra Sevastopole ietilpa Krimas APSR Krievijas PFSR sastāvā. Otrā pasaules kara laikā Sevastopoles aizstāvji apmēram 250 dienas pretojās vācu karaspēka aplenkumam 1941.-1942. gadā. Pēc Staļina nāves jaunā PSRS valdība 1954. gada 19. februārī nolēma nodot Krimas apgabalu un Sevastopoli Ukrainas PSR pakļautībā, atzīmējot 300 gadus kopš 1654. gada Krievijas caristes sadarbības līguma ar ukraiņu kazakiem Bohdana Hmeļnicka vadībā. Tomēr Sevastopole kā padomju flotes militārā bāze bija "slēgtā pilsēta", kas reāli pakļāvās PSRS Aizsardzības ministrijai.
1991. gadā Sevastopole nokļuva Ukrainas Republikas pārvaldībā, kas tai piešķīra īpašu statusu ārpus Krimas Autonomās Republikas. 1997. gadā Ukraina un Krievija parakstīja Draudzības, Sadarbības un Partnerības līgumu, kura vienojās par bijušas PSRS Melnās jūras flotes sadalīšanu un Sevastopoles kara bāzes un Sevastopoles rajona nodošanu Krievijas Federācijas pārvaldībā. Pēc promaskaviskā prezidenta Janukoviča nākšanas pie varas 2010. gada aprīlī Ukrainas parlaments pagarināja Sevastopoles kara bāzes teritorijas iznomāšanu Krievijai līdz 2042. gadam.
Pēc Eiromaidana sacelšanās un Ukrainas valdības nomaiņas 2014. gada 23. februārī Sevastopolē notika pret jauno Kijivas valdību vērsts mītiņš "pret fašismu", kurā par jauno pilsētas mēru tika pasludināts uzņēmējs Aleksejs Čalijs (Чалый). 24. februārī Sevastopoles pilsētas padomes ārkārtas sesijā viņu ievēlēja par izpildkomitejas vadītāju, kaut arī iepriekšējais pilsētas mērs Vladimirs Jacuba formāli turpināja atrasties savā amatā. 26. februārī A. Čalijs deklarēja, ka Sevastopole nepakļausies Ukrainas valdības rīkojumiem. 28. februārī karavīri bez pazīšanās zīmēm ieņēma valdības ēkas, kas iezīmēja Krimas krīzes sākumu. Starptautisko situāciju saasināja Krievijas prezidenta Vladimira Putina vēršanās pie Krievijas Valsts domes 1. martā ar lūgumu atļaut izmantot Krievijas karaspēku Krimas teritorijā.[2] Ukrainas armijas kara bāzē tika izsludināta pilna kaujas gatavība.
16. martā Krievijas karaspēka klātbūtnē Sevastopolē notika referendums, kurā pēc balsu skaitīšanas komisijas ziņām par "atkalapvienošanos ar Krieviju" nobalsoja 96,59% referenduma dalībnieku.[3] 18. martā Maskavas Kremlī A. Čalijs kopā ar Krimas premjerministru S. Aksjonovu un parlamenta spīkeru V. Konstantinovu parakstīja līgumu par Krimas un Sevastopoles iekļaušanu Krievijas Federācijas sastāvā.[4] Ukrainas valdība referendumu pasludināja par neleģitīmu.