支隊はズダ湾で黒海から来た義勇艦隊の仮装巡洋艦と合流し、１１月２６日にはスエズ運河を通過して１２月３０日にフランス領マダガスカル島のノシベ 港に入った。
本隊は１２月１９日に喜望峰を通過し、翌年（明治３８年）１月９日に支隊との合流を果たした。そこで知らされたのは１月１日に旅順要塞が陥落し、旅順艦隊の残存艦艇も事実上日本の手に落ちたことであった。
これにより日本艦隊に対する圧倒的優位を確保するという当初の回航の目的は達成困難になり遠征を中止することも考えられ、艦隊は同地にしばらくとどまることになった。
なおノシベで居座り続けていたわけではなく、ノシベから１００㎞北のアンツィラナナ （１９７５年まではディエゴ・スアレス と呼ばれていた）にも停泊したという複数の記述がある。
ロシア海軍上層部は本国に残っていた艦艇で第３太平洋艦隊を編成し、日本艦隊と砲撃力を互角に近づけることで遠征を続行することを決定した。
この知らせと制海権を奪回せよとの命令を受けたロジェストヴェンスキーは、現在の戦力では制海権の奪回は不可能で、第３太平洋艦隊は老朽艦で逆に戦力減であること、現在の戦力でウラジオストクに入り通商破壊に徹することが最良であると返答し、すぐに出航するべきであると説いた。
２月１５日に第３太平洋艦隊はリバウを出航したが、その知らせを聞いたロジェストヴェンスキーは病気と称して辞職を願ったが許されなかった。
３月１６日、第２太平洋艦隊はノシベを出航した。インド洋方面にはロシアの友好国の港は少なく、将兵の疲労は蓄積し、水、食料、石炭の不足に見舞われた。４月５日にはマラッカ海峡に入り、４月１４日にフランス領インドシナのカムラン湾に入り第３太平洋艦隊を待った。この時ロジェストヴェンスキーは本国に第３太平洋艦隊を待たずにウラジオストクへ急航したいと打電したが許可されなかった。
４月２１日にフランスより退去要求を受けたが、４月２６日にバンフォン湾（英語版）の国際法違反にならない場所で投錨した。第３太平洋艦隊は３月２６日にはスエズ運河を通過し、５月９日に第２太平洋艦隊と合流を果たした。
連合艦隊の準備
日本海軍の連合艦隊は、すでに１９０４年（明治３７年）８月１０日の黄海海戦でロシア太平洋艦隊主力の旅順艦隊に勝利し、８月１４日の蔚山沖海戦でウラジオストク艦隊にも勝利したことで極東海域の制海権を確保していた。また旅順要塞の陥落および旅順艦隊の壊滅の後、艦艇を一旦ドック入りさせるとともに、入念に訓練を行い、バルチック艦隊の迎撃殲滅に自信を付けて行った。
残る最大の問題はバルチック艦隊をどこで捕捉迎撃するかだった。ウラジオストクへの航路としては対馬海峡経由、津軽海峡経由、宗谷海峡経由の3箇所があり得た。
３箇所すべてに戦力を分散すれば各個撃破されかねないと考え、戦力を集中していずれか１箇所に賭けた。
とはいえ、バルチック艦隊が宗谷海峡を通過するためには、距離が遠いため日本本土の太平洋側沖合いで石炭を洋上補給する必要がある。
津軽海峡は日本側の機雷による封鎖が厳重になされていた。このようなことから連合艦隊司令長官東郷平八郎大将は、バルチック艦隊は対馬海峡を通過すると予測し主力艦隊を配置するとともに周辺海域に警戒網を敷いた。
１９０５年（明治３８年）２月２１日には連合艦隊旗艦三笠が朝鮮半島の鎮海湾に入り、同地を拠点に連合艦隊は対馬海峡で訓練を繰り返した。
日本側の地点表示・哨戒態勢
日本側は戦闘予想海域を直交する等間隔の直線で区切り、その交点に数字を割り振っていた。
また陸地が目標となるいくつかの地点を集合場所としてアルファベットで表示し（例：鎮海湾がＣ地点）、海峡を横切る６つの警戒線と通過する方向になる３つの幹線を設定し交点にアルファベット２文字の地点表示をつけた。
なお哨戒海域を碁盤の目のように細かく分画し、その一つひとつに哨戒用の艦船を配置したという話があり、軍籍船舶以外にも漁船まで動員した哨戒艦船７３隻で行ったという。
しかしそれに関する記述は戦史に存在しない。２７日朝に哨戒を行っていたのは第３戦隊と第６戦隊所属の防護巡洋艦「和泉」、同「秋津洲」、及び仮装巡洋艦５隻である。また配置の基準も地点ではなく警戒線である。
ジャンクを雇い入れ偽装下士卒を配置し、台湾周辺海域において漁業などを装いつつ監視を行うという指示は出されている。
これはバルチック艦隊が台湾周辺を一旦占拠する可能性に備えたものである。
連合艦隊の迷い
５月１４日、バルチック艦隊はバンフォン湾を出航した。５月１９日にはバタン諸島付近でイギリス汽船「オールドハミヤ」を拿捕した一方、日本に向かっていたノルウェー汽船「オスカル」は臨検のみで解放した。
バルチック艦隊は「オールドハミヤ」（乗員はロシア海軍の船員と交代）と仮装巡洋艦「テレーク」と同「クバーニ」を分離し、囮としてバラバラに宗谷海峡回りでウラジオストクに向かわせたが、これらは日本側に発見されずいずれもウラジオストクにたどり着けなかった。
２２日ごろバルチック艦隊は宮古海峡を通過し東シナ海に入り対馬海峡通過は確実のものとなった。ここで日本の民間船に目撃されるがその通報は海戦より遅れた（久松五勇士参照）。
バルチック艦隊は23日に洋上で停止し、各艦搭載出来得る限りの石炭を積み込んだ。
また同日にフェリケルザムが病死したがその死は秘匿され、ネボガトフにすら知らされなかった。２５日８時には仮装巡洋艦「リオン」と同「ズネーブル」を護送とし、運送船6隻を上海方面に向かわせた。
ロジェストヴェンスキーは水雷攻撃を避けるために対馬海峡を日中に突破すると決め、時間調整として２６日に艦隊運動の演習を行っている。
連合艦隊は５月２３日に日本へ到着した「オスカル」からバルチック艦隊と遭遇し、バルチック艦隊の士官から対馬海峡へ向かうと聞いたという情報を受け取ったが、１９日以降の足取りはつかめていなかった。