ソビエト連邦の崩壊の過程で、主要基地であったセヴァストポリ海軍基地の所在地であるクリミア半島がウクライナ領になったことから艦隊の帰属が宙に浮くことになった。長らく二国間で協議が進められた結果、艦隊の分割と基地の使用権に関する協定が結ばれた。この協定により、ロシア海軍は2017年（後の2010年に結ばれたハリコフ合意により2025年まで延長）までセヴァストポリに駐留することが認められた。なお、ウクライナ海軍が引き取った大型艦艇の多くは、後に天然ガスの代金の未納分で相殺する形でロシア船籍となっている。
2004年にウクライナでオレンジ革命と呼ばれる政変が起こり、ヴィクトル・ユシチェンコ政権が成立した。同政権はNATO加盟を目指すなど親西側路線を掲げる一方、ロシアに対しては2017年までに黒海艦隊を撤退させるよう要求した。しかし2010年の選挙で親露派と目されるヴィクトル・ヤヌコーヴィチ政権が成立したことにより、黒海艦隊の駐留期限をさらに25年延長する協定が結ばれた。これにより、黒海艦隊は少なくとも2042年まではセヴァストポリを母港とすることが可能となったが、そのヤヌコーヴィチ政権が崩壊した2014年にロシアはクリミア半島全域を支配下に置き、編入を宣言した。
2010年頃の黒海艦隊にとって最大の問題は艦艇の老朽化であった。旧式艦が多数在籍しており、約40隻の在籍艦艇中、稼動状態にあるものは20隻程度でしかなかった[4]。しかも、黒海はジョージアに面しており、2008年8月のロシアによるジョージア介入のような武力紛争が再び発生した場合には黒海艦隊が海上優勢の確保や輸送を担わなければならない。
このため、ロシア海軍は2020年頃までに黒海艦隊の近代化を重点的に進めることを計画し、6隻の11356M型フリゲート、6隻の636型（キロ級）通常動力型潜水艦、大型のイワン・グレン級揚陸艦2隻を含む新艦艇20隻を配備する予定であった。2022年時点、準同型艦のタルワー級を取得していたインド海軍が11356M型2隻を取得することになったため同フリゲートの取得予定は4隻に減少した。またイワン・グレン級については北方艦隊配備が優先され実現していない。
2022年ロシアのウクライナ侵攻では投入されたロシア海上戦力の主力を担っているが、反撃も受けて喪失艦艇が生じているほか、本部もウクライナの攻撃目標となっている[2]（後述）。 ロシア帝国皇帝のピョートル1世は黒海進出を企図して海軍を創設。ロシア帝国は以後、黒海周辺を支配していたオスマン帝国と数次にわたる露土戦争を戦い、オスマン帝国海軍との間に多くの海戦を行う。艦船は、次第に近代化される。 クリミア戦争後のパリ条約 (1856年)によって黒海での艦隊の保有が一時禁じられたが、1871年には条約改定で再軍備が認められ、艦隊が再建される。ただしボスポラス海峡とダーダネルス海峡の艦艇の通行は禁止された。 1904年、日露戦争勃発。黒海艦隊の出動も検討されるがイギリスなどの圧力により断念し、商船に偽装した仮装巡洋艦数隻の出動にとどまる[注 2]。 ロシア第一革命（1905年）では、戦艦ポチョムキン＝タヴリーチェスキー公上での水兵の反乱である戦艦ポチョムキンの反乱や防護巡洋艦オチャーコフ上での巡洋艦オチャーコフの反乱
歴史
1914年に勃発した第一次世界大戦では、ドイツ帝国海軍やオスマン帝国海軍との間に幾度かの大規模海戦を行う。しかし、このとき黒海方面に配備されていたのは旧式艦が主で、ロシア帝国海軍の主力はバルト海方面にあった。
大戦中の1917年3月に二月革命が起き、黒海艦隊は臨時政府の所属となる。しかし、臨時政府は十月革命とその後の紛争に敗れ壊滅し、臨時政府黒海艦隊の一部はウクライナ人民共和国軍黒海艦隊となる。また、一部は赤軍黒海艦隊となる。残る一部は白軍が掌握した。
1918年のブレスト＝リトフスク条約により中央同盟国と連合したウクライナ人民共和国が赤軍を一蹴してクリミア半島全土を掌握すると、黒海艦隊の多くはウクライナ人民共和国に接収される。一部は、ノヴォロシースクに逃れて赤軍に編入される。4月にヘーチマンの政変によりウクライナ国が成立すると、ウクライナ国海軍を構成する。これが、ウクライナの黒海艦隊の全盛期となる。ウクライナ国黒海艦隊はウクライナ独立の象徴となる一方、ドイツ帝国海軍黒海艦隊としての任務も担う。12月のドイツの降伏によりウクライナ国は崩壊しクリミア半島は白軍に掌握され、ウクライナの黒海艦隊は白軍に接収される。
1919年、クリミア半島で組織された白軍合同組織南ロシア軍に参加。1920年、南ロシア軍組織の改変により、ロシア軍黒海艦隊となる。11月には多くの艦船が国外脱出する。12月にはチュニジアでフランス政府によって艦船が差し押さえられ、ロシア軍黒海艦隊主力は消滅する。ロシア国内に残された艦艇は、多くが脱出に際し破壊された状態となる。一部の艦艇が労農赤軍によって修復される。1935年、ソビエト連邦政府により正式に黒海艦隊と命名される。
1941年に勃発した独ソ戦において、黒海艦隊は、黒海とその北岸でナチス・ドイツを主力とする枢軸国軍と激しい戦いを展開した。「黒海の戦い (第二次世界大戦)」、「コンスタンツァ襲撃」、「クリミアの戦い (1941年-1942年)」、および「クリミアの戦い (1944年)」を参照
1991年、ソ連崩壊により帰属が宙に浮く。翌1992年にクリミア共和国が独立を宣言するが、のちクリミアはウクライナ領の自治共和国となった。1997年にはロシアとウクライナ間で艦隊を分割した上で、ウクライナはロシアに対し20年間の基地使用権を与える協定が結ばれる。2005年のロシア・ウクライナガス紛争に絡み、ロシア艦隊の基地使用権が問題となる。
2008年8月、南オセチア紛争において、グルジア（現ジョージア）の分離勢力を支援するロシアは黒海艦隊をアブハジア沿岸に進出させた。グルジア海軍の4隻のミサイル艇及び哨戒艇と遭遇して交戦し、小型ロケット艦ミラージュが対艦ミサイルによりグルジア艇1隻を撃沈した（アブハジア沖海戦）。
2010年、ロシア＝ウクライナ間のハリコフ合意により、2014年を期限とする艦隊の駐留期限が2025年まで延長。ロシアからウクライナに向けた天然ガス代金の優遇措置が条件として合意されたもの[5]。
2014年ウクライナ騒乱に対して、ロシアは黒海艦隊の海軍歩兵を含めて軍事介入を行なってクリミアを制圧。半島内のウクライナ軍に対して降伏勧告と最後通牒を発した。ロシアによるクリミアの併合後、クリミアは黒海艦隊を含むロシア連邦軍の策源地となった
2015年5月に地中海へ進出して、中国人民解放軍海軍との初の合同軍事演習を実施した[6]。