在建立蘇聯黑海艦隊之前，俄國早在1783年就在黑海著手建立一支艦隊。最初是將一些艦船從亞速海(見亞速海艦隊)調到阿赫季阿爾鎮(1784年起為塞瓦斯托波爾市，1804年起成為黑海的主要軍港)附近的一個海灣。這些艦船成了後來迅速發展的俄國新艦隊的核心。在十八世紀至十九世紀進行的俄土戰爭、俄法戰爭以及俄國對其他國家的各次戰爭中，黑海艦隊多次進行了成功的戰鬥。其中，在菲多尼西島附近，在刻赤海戰(1790)，在堅德拉島附近(1790)以及在卡利亞克里亞角附近(1791)的海戰中，黑海艦隊取得了巨大的勝利。黑海艦隊的艦艇參加過達達尼爾海戰(1807)和阿索斯海戰(1807)。1853—1856年克里木戰爭期間，黑海艦隊的一支分艦隊在錫諾普海戰(1853)中摧毀了土耳其艦隊。艦隊官兵英勇地參加過塞瓦斯托波爾防禦(1854—1855)。黑海艦隊的建立、發展和勝利是與俄國的傑出的海軍統帥烏沙科夫，謝尼亞文，拉扎列夫，納希莫夫等人的活動聯結在一起的。根據巴黎和約(1856)的規定，俄國被剝奪了在黑海擁有艦隊的權利。後來，倫敦公約(1871）取消了這一限制，俄國又開始在黑海建立蒸汽裝甲艦隊。對裝甲艦隊的發展，布塔科夫和馬卡羅夫曾作出重大貢獻。第一次世界大戰爆發前，黑海艦隊共有5艘戰列艦，2艘巡洋艦，17艘驅逐艦，12艘小型驅逐艦，4艘潛艇及其他艦艇。第一次世界大戰中，艦艇的數量得到增加。黑海艦隊在黑海地區進行了對德國—土耳其的作戰；支援了高加索方面軍和羅馬尼亞(從1916年開始)方面軍的部隊；破壞敵人的海上交通線。
黑海艦隊的官兵積極參加了俄國的革命運動。1901—1902年，艦隊中建立了第一批社會民主黨組織。1904年，在塞瓦斯托波爾成立俄國社會民主工黨軍事組織的艦隊中央委員會。1905年6月，“波將金”號裝甲艦上爆發起義，11月又爆發了塞瓦斯托波爾起義(1905)。1917年二月革命以後，尤其是粉碎科爾尼洛夫叛亂以後，對各港口城市的蘇維埃，對黑海艦隊各艦艇及岸上部隊的水兵委員會，都加強了布林什維克化的工作。在得到偉大十月社會主義革命在彼得格勒取得勝利的訊息後，黑海艦隊許多艦艇上的革命官兵在會議和群眾集會上通過了承認蘇維埃政權和把艦隊轉向蘇維埃政權一邊的決議。1917年年底，在黑海艦隊中對參加妥協派蘇維埃的孟什維克、社會革命黨人、無政府主義者和資產階級民族主義分子展開了頑強鬥爭。同時，對有敵對情緒的軍官繼續進行激烈鬥爭。1917年12月，在塞瓦斯托波爾成立了布林什維克革命軍事委員會，把權力掌握在自己手中。1918年年初，艦隊的革命官兵幫助俄國南方的許多港口城市和工業城市建立蘇維埃政權。國內戰爭期間，他們在亞速海區艦隊、伏爾加河區艦隊和第聶伯河區艦隊為保衛蘇維埃政權進行了英勇的戰鬥。由於艦隊的艦艇有被德—奧佔領軍奪走的危險，部分艦艇於1918年轉移到黑海東北岸的各港口。後來按照蘇維埃政府的命令，在新羅西斯克和圖阿普謝地區將這些艦艇沉掉。留在塞瓦斯托波爾的艦艇則被德國佔領軍和烏克蘭民族主義分子奪去。1919年春，恢復了克里木半島的蘇維埃政權。但該半島很快又落到白衛軍手中。1920年5月，根據共和國革命軍事委員會的命令，以這年3月建立的西南方面軍海上和江河部隊為基礎，組建了黑海與亞速海海軍。這支海軍參加了對白衛軍的艦艇和陸軍部隊的戰鬥，但由於兵力不足，當弗蘭格爾將軍的白衛軍於1920年年底從克里木逃走時，未能阻住白衛軍劫走艦隊的主要艦艇。根據俄國共產黨(布)第十次代表大會(1921)的決定，開始恢復和鞏固黑海的蘇維埃艦隊。經過修理編入艦隊的有2艘驅逐艦，5艘炮艦，2艘潛艇，數艘掃雷艦艇和佈雷艦(1922)，“共產國際”號巡洋艦(1923)和“紅色烏克蘭”號巡洋艦(1927)。艦隊開始進行有計劃的戰鬥訓練。到1928年，艦隊的恢復工作基本結束，並開始技術改造工作。同時，從波羅的海艦隊調來一些艦艇，使艦隊不斷得到加強。1929—1930年，“巴黎公社”號戰列艦和“赤色職工國際”號巡洋艦(後來分別改名為“塞瓦斯托波爾”號戰列艦和“紅色克里木號”輕巡洋艦)調到黑海。
蘇聯人民委員會1935年1月11日決定，把黑海和亞速海海軍改名為黑海艦隊(主要基地為塞瓦斯托波爾)。在戰前的幾個五年計劃期間，黑海艦隊補充了數十艘各種新的戰鬥艦艇和許多輔助船隻。建立了航空兵、海岸防禦配系和防空配系。到蘇德戰爭開始時，黑海艦隊共有1艘戰列艦，6艘巡洋艦，3艘驅逐領艦，14艘驅逐艦，47艘潛艇，4艘炮艦，2個魚雷艇支隊，數個掃雷艦艇大隊、護衛艇大隊和獵潛艇大隊，以及其他艦艇和船隻。艦隊航空兵共有各種飛機625架。此外，多瑙河區艦隊(1941年11月20日前)和1941年7月重新組建的亞速海區艦隊也編入黑海艦隊。
蘇德戰爭一開始，黑海艦隊就用艦炮和海岸炮的火力支援陸軍兵團和軍團進行防禦戰鬥和濱海方向的作戰。艦隊航空兵對羅馬尼亞王國的一些重要海軍基地、港口和油田進行了突擊。艦隊的編隊和部隊參加了運送登陸兵上陸、保衛海軍基地和破壞敵海上運輸等戰鬥活動。1941年8—10月，黑海艦隊先後積極參加了敖德薩防禦和塞瓦斯托波爾防禦。黑海艦隊參加過具有重大意義的刻赤—費奧多西亞登陸戰役(1941—1942)。在高加索會戰(1942—1943)中，艦隊的艦艇、部隊和編隊的全體人員，在保衛新羅西斯克、運送登陸兵在南奧澤列伊卡和斯坦尼奇卡(見梅斯哈科)上陸的戰鬥中、在堅持7個月之久的小地英勇保衛戰中、在新羅西斯克—塔曼戰役(1943)，刻赤—埃利季根登陸戰役(1943)中都表現得十分勇敢頑強，顯示了高超的作戰技能。艦隊的兵力曾支援在濱海方向進攻的集團軍和方面軍，破壞敵人海上交通線和保障軍事運輸和國民經濟運輸。1944年，黑海艦隊的編隊和部隊積極參加了敖德薩戰役、克里木戰役和雅西—基什尼奧夫戰役。亞速海區艦隊支援陸軍解放了塔甘羅格、馬裡烏波爾(日丹諾夫)和奧西片科(別爾江斯克)，同時還完成了許多其他重要任務。1944年4月在亞速海區艦隊的基礎上重新建立的多瑙河區艦隊從多瑙河河口一直打到維也納。
戰爭期間，黑海艦隊擊沉、擊傷數百艘敵人的戰鬥艦艇、輔助船隻和運輸船。艦隊航空兵、艦炮和海岸炮殲滅敵人大量的支撐點、有生力量和軍事技術裝備。黑海艦隊完成了約200萬人及800多萬噸軍用物資和民用物資的海上運送任務。在對敵作戰中，艦隊全體官兵樹立了英勇無畏和掌握高超軍人技能的榜樣。在黑海艦隊勝利完成各項戰鬥任務過程中，經常開展的有針對性的黨政工作，對於黑海艦隊勝利完成各項戰鬥任務起了巨大作用。
由於戰爭中出色完成上級交給的任務，以及作戰英勇無畏和表現出高度的組織性和紀律性，全艦隊的艦艇、部隊和編隊中共有18個單位榮獲近衛稱號，59個單位榮獲勳章，44個部隊和編隊被授予榮譽稱號。黑海艦隊數千名官兵因戰功卓著而榮獲勳章和獎章，其中200多人被授予蘇聯英雄稱號。
五十年代至六十年代，黑海艦隊補充了各種新的艦艇、飛機、導彈和其他現代化武器和技術器材。黑海艦隊各兵種在數量和品質上的提高，大大提高了艦隊的威力和戰鬥準備水平，使艦隊能夠勝任新的任務。黑海艦隊的艦艇開始到地中海和世界大洋進行遠航和遠征。艦隊官兵在“海洋”大演習和其他一系列演習中表現出很高的海戰素養。為了表彰黑海艦隊在衛國戰爭中的戰鬥功勳、集體英雄主義和勇敢精神，在慶祝蘇聯人民取得這次戰爭勝利二十週年之際，蘇聯最高蘇維埃主席團1965年5月7日釋出命令，授予黑海艦隊紅旗勳章。艦隊的許多艦艇、部隊和編隊榮獲蘇聯共產黨中央委員會、蘇聯最高蘇維埃主席團和部長會議授予的獎旗、列寧誕辰紀念獎狀和獎章，以及蘇聯國防部長授予的“勇敢和軍人英勇精神”獎旗。
歷任司令：1917年7—12月為涅米茨；1918年3—5月為薩布林(後叛變)；1919年4—6月為舍伊科夫斯基；1920年3—5月為伊茲梅洛夫；1920年5—12月為東布羅夫斯基；1920年12月—1921年12月和1925年1月—1926年10月為潘採爾然斯基；1921年12月—1922年8月為馬克西莫夫；1922年8月—1924年6月為韋克曼；1924年6—12月為維克托羅夫；1926年11月—1931年6月為奧爾洛夫；1931年6月—1937年10月為科扎諾夫(1935年起為二級艦隊級)；1937年10—12月為斯米爾諾夫(二級艦隊級)；1938年1月—1939年3月為尤馬舍夫(二級艦隊級)；1939年3月—1943年5月和1944年3月—1948年11月為奧克佳布里斯基(二級艦隊級，1941年起為海軍中將，1944年4月起晉升為海軍上將)；1943年5月—1944年3月為弗拉基米爾斯基海軍少將(1944年3月起晉升為海軍中將)；1948年11月—1951年8月為巴西斯特海軍中將(1949年5月起升晉為海軍上將)；1951年8月—1955年7月為戈爾什科夫海軍中將(1953年8月起晉升為海軍上將)；1955年7—11月為帕爾霍緬科海軍中將；1955年12月—1962年2月為卡薩託諾夫海軍上將；1962年7月—1968年12月為丘爾辛海軍中將(1964年起晉升為海軍上將)，1968年12月—1974年3月為瑟索耶夫海軍中將(1970年11月起晉升為海軍上將)；1974年3月起為霍夫林海軍中將(1976年2月起晉升為海軍上將)。