Регіон сучасного Севастополя був заселений людиною близько 100 тисяч років тому, під час останнього заледеніння. У печерах і гротах кримських передгір'їв жили тоді неандертальці. Близько 40-30 тис. років тому них перемінили люди сучасного фізичного вигляду - кроманьонці. Близько 20 тис. років тому льодовик став танути - на Землі почалося глобальне потепління. 10 тис. років тому клімат став близький до сучасного. У регіоні Севастополя знайдені стоянки людини епохи верхнього палеоліту, мезоліту, неоліту, бронзового століття. Близько 10 століття до н.е. у Криму почався ранній залізний вік. Приблизно в цей час (або трохи раніше) на півострів стали заходити ще поки дуже рідкі грецькі кораблі, а народи, що жили в кримських степах стали робити набіги на країни Межиріччя і Кавказу - Урарту, Митанні й Ассирію. З тих пір ми знаємо народи Криму по іменах; закінчується доісторичний і починається історичний період. Кочівники-кіммерийці - перший кримський народ, ім'я якого збереглося в аналах історії. Однак, їхніх стоянок у регіоні Севастополя не виявлено. Зате наступний за часом кримський народ - таври - зв'язаний з історією Південно-західної Таврики дуже і дуже тісно.

Таври, про появу яких у Криму відомо мало (вони з'являються як би раптово біля ІХ в. до н.е.), займали гірську частину Криму, Південний берег і частину передгір'їв. У цих важкодоступних місцях вони і тримали оборону від завойовників протягом десяти наступних століть. Протягом останніх десятиліть в історичній науці не припиняється суперечка: один чи народ проживав на території, що прийнято вважати життєвою зоною таврів. Справа в тім, що в різних таврських поселеннях можна простежити два типи матеріальної культури: власне таврську, більш примітивну, і так називану "кизил-кобінську", названу по імені поселення в печери Кизил-Коба на схилах Чатирдага, де вона була уперше виявлена. Прихильники існування двох народів на одній території, причому зони їх життя вигадливо перемішуються, не можуть пояснити головного: чому греки, що відмінно знали таврів, багато про них писали, століттями жили з ними пліч-о-пліч, безупинно воювали, напевно перетворювали в рабство, не мали ні найменшого представлення про "кизил-кобінців" і жодного разу їх не згадують. Історики, що підходять до цього питання виважено, визнають існування розходжень у матеріальній культурі  таврських племен, одні з яких, більш розвиті, проживали в родючих річкових долинах і, видимо, випробували визначений культурний вплив сусідніх народів - греків і скіфів. Інші племена, з більш строгими і консервативними звичаями, займали важкодоступні гірські райони і від контактів с сусідами намагалися ухилятися, відносячись до них підкреслено вороже.

На узбережжі Балаклавської бухти знаходилося поселення одного з таврських племен, що займалося не тільки мотичним землеробством і відгінним скотарством, але і рибальством, і піратством. У  прибережних таврів піратство було поширено як підсобний промисел. Узятих у полон моряків місцеві аборигени приносили в жертву своїй головній богині Діві, скидаючи них зі скелі, на якій знаходилося святилище божества. Припускають, що храм Діви знаходився в районі мису Феолент. З таврським храмом Діви зв'язаний один зі знаменитих давньогрецьких міфів - про приношення в жертву богині Артеміді (з якої греки ототожнювали Діву) дочки царя Агамемнона Іфігенії. Артеміда пошкодувала дівчину і з жертовного столу перенесла неї в Тавриду, у храм, де богині поклонялися таври. Іфігенія стала жрицею цього храму. На виторг дівчині відправився її брат Орест, якому після небезпечних пригод удалося викрасти сестру з храму і повернутися з нею на батьківщину. Цей міф був дуже популярний у Древній Греції і Римі: його мотиви використовувалися в монументальному живописі, у розписі ваз, у драматургії:  один з найбільших древніх авторів Еврипід написав трагедію "Іфігенія в Тавриді". Інше велике таврське  поселення в околицях Севастополя - Уч-Баш - було розкопано в нижньому плині ріки Чорної.

Суспільний пристрій таврів був первіснообщинним; рідоплимінний лад і звичаї цього народу відрізнялися особливою стійкістю. Вони свідомо ізолювали себе від сусідів, і тільки в пізню епоху в таврських могильниках стали зустрічатися вкрай нечисленні скіфські, грецькі і північнокавказькі предмети. На початку нової ери тавров постійно тіснили скіфи, грекі і сармати, що з'явилися в Криму, чому таври поступово асимілюються з ними і зникають як самостійний народ. Зникає і їхня матеріальна культура. Скіфи, кочові племена, що говорили, як і таври, мовою іранської групи, з'явилися в Східному Криму в VII в. до н.е., а в Західному - у VI-V в.в. до н.е.

Скіфи були одним із самих могутніх, а тому, знаменитих кочових народів стародавності. Вчасно їхньої появи в Південно-західної Тавриці, скіфи знаходилися в стадії розкладання первіснообщинного ладу, зародження класів і примітивної державності. На V-IV в.в. до н.е. приходиться епоха розквіту Скіфського царства, що спочатку було союзом племен, а потім  дійсно перетворилося в ранньодержавне утворення зі своєю столицею і соціальною ієрархією. Скіфське царство епохи розквіту займало величезну територію: усі степи і лісостепу від дельти Дунаю на заході до нижнього плину Дону на сході. При самому знаменитому скіфському царі Атеє столиця їхньої держави знаходилася в так називаному Каменському городищі в Нижньому Подніпров'ї. Це величезне поселення, що містить в собі риси міста і кочового стійбища, займало сотні гектарів, а його земляні зміцнення могли вмістити десятки тисяч пастухів і рабів-ремісників, сотні тисяч голів худоби.

Скіфи поділялися на кілька племінних об'єднань, самими численними з яких були Царські скіфи, що панували над іншими родичами, сайі. У зону їхнього впливу і влади потрапив, починаючи з VII в. до н.е. і Степовий Крим. Поки Скіфія була величезна і сильна, поки вона була здатна давати відсіч будь-якому ворогові, навіть перському цареві Дарієві, її правителі не перешкоджали підставі на їхніх землях грецьких колоній. Навпаки, з такого сусідства вони покористувалися: з Ольвією і  містами Боспорського царства скіфи вели оживлену торгівлю і, видимо, стягували данина, впливали на політичне життя. Свідченням тому може служити чудовий скіфський царський курган Куль-Оба IV в. до н.е., розкопаний у 1830 році під Керчю. Причина, по якій похований під курганом вождь не був відвезений на традиційне місце поховання знатних скіфів, невідомо. Але, судячи зі знахідок, ховав його весь Пантікапей.

На Південно-Західний Крим, де тільки зароджувалася Херсонеська держава, скіфи уваги майже не звертали. Коли ж наприкінці IV в. до н.е. скіфів стали тіснити зі сходу сармати, а з заходу македонянці і фракійці, їхня держава скулилася, і під владою скіфських царів залишилися тільки Нижнє Подніпров'я і степовий Крим. Столицю свою вони перенесли в центр півострова, на вершину Петровських скель, заснувавши там місто Неаполь Скіфський. З тих пір вони волею-неволею повинні були тісно взаємодіяти зі своїми сусідами. Про те, яку роль зіграли скіфы в історії Херсонеса і Гераклєйського півострова, буде розказано у відповідних розділах. Відзначимо лише, що з моменту виникнення в Північне Причорномор'я грецьких колоній, тобто з VII-VI в.в. до н.е., скіфська історія і культура були найтіснішим образом переплетені з грецькою. Незважаючи на наявність власних багатих традицій образотворчого і прикладного мистецтва, що характеризувалося так називаним “звіриним стилем” (скіфи дуже любили прикрашати свої вироби зображеннями фантастичних і реальних тварин), скіфські царі і знать у масовому порядку замовляли зброю, посуд і прикраси ювелірам Ольвії і Пантікапея, вивчали грецька мову і лист. В архітектурі оборонних споруджень, суспільних будинків Неаполя Скіфського і будинків місцевої знаті почувається найсильніший грецький вплив, хоча велика частина міської забудови це - лабіринти хатин і напівземлянок скіфської бідноти.

Починаючи з IV в. до н.е. скіфи, що жили в Криму, особливо ті, хто розселився в передгір'ях, стали активно переходити від кочового скотарства до осілого землеробства. До цьому їх усіляко заохочували і примушували царі і знать, тому що чудова кримська пшениця користувалася величезним попитом на тодішньому світовому ринку. Царі Боспору наживали величезні бариші на експорті десятків тисяч тонн добірного хліба, вирощеного працею осілих на їхніх землях скіфських хліборобів. І царі власне Скіфії жадали одержати свою частку доходів. Для цього їм потрібні були нові землі і власні порти. З могутністю Боспору скіфи справитися не могли, хоча і намагалися. Тому вони звернули свій погляд на південний захід - туди, де ріс і багатів заснований у VI-V в. до н.е. Херсонес.