В задачи базы входили: обеспечение рассредоточения и манёвренного базирования сил; поддержание благоприятного оперативного режима в своей операционной зоне; оборона базирования кораблей, обеспечение их развёртывания и возвращения в пункты базирования; защита судоходства; охрана государственной границы в подводной среде. Значимость базы была существенно повышена в связи с включением в её состав соединения ракетных катеров. Нависающее положение базы над главным направлением действий группировок флота — зоны Черноморских проливов (Босфор и Дарданеллы), позволяло планировать использование сил Крымской ВМБ в действиях флота по уничтожению подводных лодок и кораблей противника в юго-западной части Чёрного моря и по блокадным действиям пролива Босфор[3].
В первые годы своего существования база находилась под личным управлением главнокомандующего ВМФ СССР Сергея Георгиевича Горшкова. В 1976 году на должность командира базы был назначен контр-адмирал Юрий Викторович Крылов. При его непосредственном участии были спланированы и выполнены проекты здания штаба, тыла Крымской базы, улиц, проспекта и приморского парка в Новоозёрном. Также в этом время в составе базы служил контр-адмирал Фёдор Иванович Кантур в должности начальника политического отдела. В честь Кантура в посёлке была названа одна из улиц. в 1979 году командиром базы был назначен Игорь Георгиевич Махонин, который позже стал контр-адмиралом[4].
В 1983 году базу возглавил Игорь Васильевич Кудряшов, который до этого работал в должности начальника штаба, а позже дослужился до звания вице-адмирала. Затем, в 1987 году гарнизон возглавил капитан 1-го ранга Алексей Иванович Фролов. В конце 1980-х и начале 1990-х штаб базы возглавлял Борис Борисович Кожин, а в марте 1992 года на некоторое время стал командиром базы. Затем он стал командующим ВМС Украины. В 1992 году командиром базы стал Александр Сергеевич Цубин[4].
До момента расформирования корабли базы несли боевую службу в Чёрном и Средиземном морях, в западной Атлантике, в Красном море и Персидском заливе, где выполняли задачи охраны судоходства и боевого траления. В период с 1976 по 1996 годы корабли базы совершили 118 выходов на боевую службу, где находились 11 540 суток и прошли 788 130 морских миль, сделав при этом 94 деловых захода в 18 портов девяти стран мира[3].
В начале 1990-х годов корабли Крымской ВМБ обеспечивали действия отрядов боевых кораблей флота в районе Кавказского побережья, осуществляли эвакуацию гражданского населения из Сухуми. С конца 1994 года база начала передачу ВМС Украины кораблей, техники, оборудования, вооружения, боеприпасов и материальных средств, после чего была 1 мая 1996 года расформирована[3].
9 июля 1996 года на месте Крымской военно-морской базы была сформирована Южная военно-морская база ВМС Украины, прекратившая своё существование в марте 2014 года.
Была вновь сформирована 1 декабря 2014 года. Штаб объединения находится в Севастополе, в том месте, где ранее находился штаб ВМС Украины. Командиром ВМБ назначен капитан 1 ранга Юрий Земский.
В зону её ответственности вошло Чёрное море от границы с Украиной на западе и до Керченского пролива на востоке. В состав базы включены 41-я бригада ракетных катеров, 68-я бригада кораблей охраны водного района и 197-я бригада десантных кораблей, а также формирования боевого и тылового обеспечения[5][6].
В ноябре 2019 года торжественно получила боевое знамя нового образца[7].