„Bismarck” wyszedł w morze z Gdyni 19 maja 1941, po czym, po dołączeniu „Prinza Eugena” i eskorty niszczycieli oraz przerywaczy zagród minowych, zespół wziął kurs na Wielki Bełt. 21 maja rano okręty niemieckie zakotwiczyły w fiordzie koło Bergen. Zmieniono wówczas charakterystyczny kontrastowy kamuflaż bałtycki okrętów, z biało-czarnymi skośnymi pasami, na jednolite jasnoszare malowanie. Okręty niemieckie zostały jednak wykryte w fiordzie przez brytyjski samolot rozpoznawczy i w obawie przed brytyjskim nalotem admirał Lütjens zrezygnował z uzupełnienia paliwa przez pancernik i wieczorem okręty wyszły w morze.
Niemiecki zespół po opuszczeniu fiordów Bergen skierował się na północ, w kierunku wyspy Jan Mayen. 22 maja rano odesłano trzy niszczyciele eskorty do Trondheim, po czym „Bismarck” i „Prinz Eugen” kontynuowały rejs samodzielnie. Admirał Lütjens, korzystając z pogorszenia pogody, obrał kurs na zachód, chcąc jak najszybciej przedrzeć się na Atlantyk przez Cieśninę Duńską między Islandią a Grenlandią.