У 1936 році на базі севастопольського морського судоремонтного заводу ім. Серго Орджонікідзе утворилася нова футбольна команда "Суднобудівник". З неї-то і почався савастопольський клубний футбол, що припинився лише на деякий час із-за Великої вітчизняної війни. Команда виступала в чемпіонатах і Кубках РРФСР, а також Криму, переможцем якого стала в 1947 році. У 1949 році севастопольська команда була включена в Чемпіонат СРСР по футболу серед команд майстрів другої групи.
У 1954 від Севастополя виступала флотська команда СЬКЧФ, а в 1966-1967 роках «Чайка».
Починаючи з 1971 року севастопольські футболісти - вже незмінні учасники другої ліги чемпіонатів СРСР. Кращим досягненням стало шосте місце в 1981 і 1982 роках. Тоді тренером команди був відомий фахівець А.Н. Заяєв. Багато севастопольців виступали за команди вищої і першої ліг, за збірну СРСР. Всього в другій лізі СРСР севастопольці зіграли 926 ігор, з них 316 перемог, 248 нічиїх і 362 поразки (забито 1019 м'ячів, попущене 1095).
Починаючи з 1992 року севастопольці - учасники чемпіонатів України, в яких особливих успіхів не добивалися. У першому ж сезоні команда попала в першу лігу, але затриматися там не змогла і опустилася в другу. Виступаючи там, найвищим досягненням стало шосте місце в сезоні 1992/1993. Далі команда успіхів не добивалася. У 1996 році Севастополь на рік залишився без "великого" футболу. Потім три сезони від Севастополя виступала флотська команда "Чорноморець". У сезоні 2000/2001 Севастополь знову залишився без футболу.
Він повернувся вже наступного року, в сезоні 2001/2002. Повернувся в особі "Чайки" ВМС. Повернувся, здавалося, щоб знову піти. Команда виступала з рук геть погано, програвала матч за матчем. Команда переживала серйозні фінансові проблеми, глядачів на трибунах ставало все менше і менше. І у результаті зайняла останнє місце в групі, без права на життя. За підсумками сезону клуб повинен був знов розлучитися з Чемпіонатом України.
Цього сезону президентом клубу став А.Л. Красильников, президент "Кримнефтесервіса", який став головним спонсором клубу. Він узяв на себе всі проблеми клубу, розрахувався з боргами.
І саме з цієї миті починається історія нової севастопольської команди. У липні 2002 року був зареєстрований Професійний Футбольний Клуб "Севастополь". Команда була відразу зарахована в другу лігу Чемпіонату України по футболу. Історію команди було вирішено почати з білого аркуша. Тренувати команду був запрошений відомий і дослідний фахівець В.П. Петров. Також були запрошені ряд відомих і дослідних гравців, таких як Сергій Леженцев, Андрій Опарін, Олександр і Геннадій Кунденки, Сергій Эсін, Дмитро Назаров та інші. Саме їм було доручено створити нову команду
Першим сезоном в історії ПФК "Севастополь" став сезон 2002/2003. Початок видався дуже важким, не було ще ігрових зв'язків, взаєморозуміння між гравцями. І, як наслідок, чотири поразки в чотирьох матчах, найобразливішою з яких стала поразка на очах своїх уболівальників в кубковій грі з одеським "Чорноморцем" - 0:6.
Перший же успіх прийшов в 4-ом турі, 25 серпня 2003 року, коли ПФК "Севастополь" в домашній грі переміг "Титан" з Армянська. Далі до кінця першого круга "Севастополь" на своєму полі не потерпів жодної поразки. Лише ось до виїзних успіхів команди справа ніяк не доходила. Він прийшов в 13-ом турі, 27 жовтня 2003 року, коли "Севастополь" добув перше виїзне очко в грі з "Металургом-2" в Запоріжжі. А перша виїзна перемога була взята вже в 15-ом турі, коли команда, за підтримки своїх вболівальників перемогла "Кристал" з Херсону
На цьому закінчився перший круг першого чемпіонату в історії клубу, а команда зайняла 7-е місце в турнірній таблиці. І знову настала неясність. У перерві між кругами з команди пішли брати Кунденки, Д.Назаров, С. Есин, розлучилися з кращим бомбардиром клубу за підсумками круга К.Сизовим.
Але, як мовиться, на цьому життя не закінчується. Команда отримала хорошу і міцну фінансову основу, завдяки президентові клубу, президентові Федерації Футболу Севастополя і депутатові міського Совета А.Л. Красильникову. Був організований повноцінний 72-денний командний збір. Був створений найближчий резерв - команда "Авліта", яка виступає на чемпіонат Севастополя. Було проглянуто близько 50-ти футболістів. Всі футболісти, що знаходилися на перегляді, забезпечувалися житлом і амуніцією.
Другий круг почався вдало, з перемог. Але все таки втрата такого числа дослідних футболістів не могла позначитися непомітно. Середина і кінцівка круга прошла дуже напружено, слідством чого з'явилося 9-е місце за підсумками чемпіонату.    Та все ж ПФК "Севастополь" зробив великий крок вперед вже в першому ж сезоні і найголовніший - на севастопольські трибуни повернувся глядач, а це головне.
Зараз же севастопольці проводять свої домашні матчі у Бахчисараї, і продувжуватиметься це мабуть аж до тих пір, доки не буде добудований власний стадіон у Балаклаві.
Останній раз Севастополь на виїзді грав саме з Десною у Чернігові, і спромігся добути нічию - 1:1. У деснянців вже за такою собі традицією у ворота "моряків" забив Ярослав Сердюк, який і напередодні цього матчу обіцяв докласти як можна більше зусиль, що б спробувати вразити ворота гостей і цього разу :)