Начал играть в чемпионатах СССР в 1960 году, до 1978 года выступал в классе "Б" чемпионата СССР. До конца СССР играл во второй лиге.
При формировании нового чемпионата России получил возможность выступать в первом дивизионе, где на второй сезон стал победителем Западной зоны, но не смог в переходном турнире войти в тройку.
В 1994 году снова стал победителем дивизиона по новому регламенту, без разделения на зоны и получил право играть в элите российского футбола.
Выступал в Высшей лиге до 2001 года. Самое высокое место, которое удалось завоевать — шестое, в 1997 и 2000, это позволило клубу выступить в Кубке УЕФА сезона 2001/02. В первом же раунде Черноморец был выбит испанской "Валенсией", результаты матчей 0:1, 0:5.
2001 - в первенстве клуб постигла неудача и сезон он закончил на последнем месте.
В 2002 году "Черноморец" снова выигрывает чемпионат первого дивизиона,
2013 г. - снова вылетает из высшей лиги
2013 г. - доходит до финала Кубка РФПЛ, единственный розыгрыш которого прошёл в том году.
В 2005 году клуб лишился лицензии. Переименованный в ФК "Новороссийск", клуб выступал в любительской лиге и, выиграв соревнования зоны "Юг", вновь получил право выступать во втором дивизионе.
В 2007 году "Черноморец" занял первое место в зоне "Юг" второго дивизиона и продвинулся в Первый дивизион.
2009 году "Черноморец" отправились во второй дивизион.
В 2010 году который клуб провел в зоне "Юг" второго дивизиона, команда за три тура до финиша обеспечила себе первое место и выход в первый дивизион. Также в 2010 году "Черноморец" стал победителем Кубка ПФЛ среди победителей зон Второго дивизиона, который после расформирования ПФЛ останется в клубе на постоянной основе.
В сезоне ФНЛ 2011/2012 команда заняла 18-е место и перешла во Второй дивизион. Клуб покинули практически все футболисты за исключением - Миносяна и Григоряна. В межсезонье команду возглавил Олег Долматов. Ему удалось с нуля создать команду, которая в сезоне 2012/13 годов долгое время лидировала в зоне "Юг", но в последний момент позволила догнать себя назранскому "Ангушту". Команда из Ингушетии лишь по дополнительным очкам при равенстве очков опередила новороссийцев и перешла в первый дивизион.
В следующем сезоне 2013/14 годов "Черноморец", с отрывом в пять очков уступил первое место астраханскому "Волгарю".
В сезоне 2014/15 годов "Черноморец" стал третьим.
2019/2020 - первенство ПФЛ, зона "Юг" - 4 место из 16 (чемпионат был прерван досрочно из-за пандемии коронавируса).
Кубок 2020/2021 - групповой раунд (1/32 - 1/16 финала)
2020/2021 - первенство ПФЛ, 1 группа, 2 место из 17
Кубок 2021/2022 - 1/128 финала (техническое поражение 0:3 - игра была отменена, так как в "Черноморце" был выявлен коронавирус)
2021/2022 - первенство ФНЛ-2, 1 группа, 5 место из 17
Кубок 2022/2023 - 1/32 финала
2022/2023 - Вторая лига, 1 группа, 1 место из 14 - выход в Первую лигу
Достижения:
Чемпион РСФСР 1988
Обладатель Кубка РСФСР: 1988
1-е место в зоне Второй лиги: 1969, 1988, 1989
1/16 финала в Кубке СССР : 1989/90, 1991/92
6-е место в Высшем дивизионе: 1997, 2000
1-е место в Первом дивизионе: 1993, 1994
2-е место в Первом дивизионе (выход в Высший дивизион): 2002
