Історія освіти севастопольського футболу почалася в 1912 році, коли при безпосередній участі севастопольців був заснований Всеросійський футбольний Союз, який у свою чергу став повноправним членом ФІФА.
У 1923 році в Севастополі з'явилося перше футбольне поле, а на базі севастопольського морського судноремонтного заводу утворилася перша футбольна команда «Південний металіст». З цього почалося зростання севастопольського футболу. Протягом багатьох років футбольна збірна Севастополя була однією з найсильніших команд в СРСР. Проводилося багато міжнародних матчів. Також збірна Криму складалася в основному з севастопольських футболістів.
У 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-е місце за підсумками чемпіонату.
І все ж ПФК "Севастополь" зробив великий крок вперед вже в першому ж сезоні і найголовніше - на севастопольські трибуни повернувся глядач, а це головне.