Pada Pukul 02:00 tanggal 19 Mei, Bismarck beserta 2.221 kru yang bertugas bergegas meninggalkan Pelabuhan Gotenhafen menuju Samudra Atlantik untuk melaksanakan Operasi Rheinubung. Bismarck kemudian bertemu dengan Prinz Eugen pada pukul 11.25 yang berlayar secara terpisah dari Tanjung Arkona pada malam sebelumnya pukul 21:18. Kedua kapal tersebut dikawal oleh 3 kapal penghancur yakni Z10 Hans Lody, Z16 Frederick Eckoldt, dan Z23. Luftwaffe juga menyediakan pengawalan udara selama Bismarck berada di perairan Jerman.Â
Pada malam 20 Mei, Kapten Lindemann memberi tahu awak Bismarck tentang misi dan tujuan dari Operasi Rheinubung melalui pengeras suara. Dalam pengumumannya, Lindemann menyatakan bahwa Bismarck dan Prinz Eugen akan melewati rute yang tidak biasa. Yakni ke utara melewati Norwegia untuk mengisi perbekalan, lantas berbelok ke barat melintasi Selat Denmark yang terletak diantara Islandia dan Greenland, untuk akhirnya berbelok ke selatan Menuju Samudra Atlantik Utara. Satu jam kemudian, Bismarck dan Prinz Eugen mendapat kontak kapal perang Swedia yang tengah membayangi mereka di sekitar perairan swedia. Kapal itu ternyata adalah Kapal Penjelajah Swedia, HSwMS Gotland yang membayangi Armada Jerman selama dua jam.
Lutjens dan Lindemann menganggap bahwa Kerahasiaan Operasi telah hilang setelah kedua Kapal dibayang-bayangi oleh Gotland. Namun, OKM bersikeras tetap melanjutkan operasi tersebut dengan alasan Inggris sepertinya belum mendapatkan informasi apapun tentang Operasi Rheinubung. Hal ini dikarenakan menurut pengintaian Armada Udara Jerman, kekuatan utama AL Kerajaan Inggris berupa 1 kapal Induk, 3 kapal Perang, dan juga 4 kapal penjelajah tetap berlabuh di Markasnya di Scapa Flow.
Bismarck dan Prinz Eugen berhasil mencapai Grimstadfjord, Norwegia pada Siang Hari tanggal 20 Mei 1941. Sehari setelahnya, sebuah pesawat Supermarine Spitfire milik Inggris berhasil mengintai Bismarck dan mengambil foto dari ketinggian 8.000m. Segera Setelah adanya laporan tentang kehadiran Bismarck dan Prinz Eugen di Norwegia, AL Inggris langsung memerintahkan dua kapal tempur Utama mereka yakni Sang Ikon AL Kerajaan Inggris "HMS Hood" dan juga "HMS Prince Of Wales" yang baru berusia 2 bulan untuk berlayar menyusul 2 kapal Penjelajah Inggris "HMS Suffolk" dan "HMS Norfolk" yang tengah berpatroli di selat Denmark. Saat Prince Of Wales Diberi perintah tersebut, ia sedang melakukan proses fitting senjata di Scapa Flow. Bahkan, banyak Teknisi Sipil yang akhirnya harus ikut berlayar dikarenakan harus menyelesaikan proses fitting Prince Of Wales secepat mungkin. Untuk mengawal kedua kapal perang kebanggan Inggris tersebut, 6 Kapal Perusak juga disertakan untuk menjaga Hood dan Prince Of Wales dari serangan Kapal Selam Jerman. Sedangkan, sisa armada utama Inggris yang lain ditempatkan di Scapa Flow dalam status siaga tinggi. 8 pesawat pembom juga turut dikirim untuk menyerang Bismarck yang tengah bersauh di Norwegia. Namun, operasi tersebut gagal akibat cuaca buruk.
Pada malam hari tanggal 21 Mei Pukul 19:30, Bismarck dan Prinz Eugen meninggalkan Bergen, Norwegia menuju samudra arktik. Bismarck memimpin di depan sedangkan Prinz Eugen ditempatkan di belakang Bismarck. Pada tengah malam, Hitler akhirnya mendengar tentang Operasi Rheinubung dari perwira Kriegsmarine, Erich Raeder. Meskipun merasa kesal karena ia tahu rencana ini memiliki resiko besar yang akan membuatnya kehilangan kapal tempur kesayangannya yang baru berusia sekitar setahun. Tetapi Hitler tak mampu berbuat apapun, dikarenakan Bismarck dan Prinz Eugen telah berlayar jauh di luar jangkauan wilayah Kriegsmarine menuju samudra Arktik. Dengan berat hati, ia pun menyetujui rencana tersebut melalui surat Izin yang dikirim via telegraf kepada Laksamana Gunther Lutjens.
Pada tanggal 23 Mei 1941 pukul 19:22, Bismarck beserta Prinz Eugen mendapat kontak di radar mereka yang ternyata merupakan kapal Penjelajah Inggris "HMS Suffolk". Lutjens memberi izin kepada Prinz Eugen untuk menembakkan meriamnya kearah Suffolk. Tetapi Suffolk malah mundur dan menghilang dari pandangan kedua kapal perang Jerman.Â
Pada pukul 20:30 HMS Suffolk bergabung dengan HMS Norfolk untuk kembali mencoba mendekati Bismarck dan Prinz Eugen, Tetapi mereka mendekati Bismarck dan Prinz Eugen dengan jarak yang terlalu dekat. Tak ingin menyia-nyiakan kesempatan, Seketika itu Juga Bismarck melepaskan 5 tembakan meriam utamanya kearah musuh. Meskipun 3 dari 5 tembakan meriam tersebut nyaris mengenai Norfolk dan menyebabkan hujan Serpihan Amunisi diatas dek Suffolk. Namun, guncangan dari salvo meriam utama 38cm Bismarck yang sangat menggelegar itu justru merusak Radarnya sendiri. Hal ini menyebabkan Bismarck ditarik posisinya ke belakang, dan Prinz Eugen mengambil alih posisi Bismarck untuk memimpin di depan. Sejam kemudian, Suffolk dan Norfolk berhasil menghindar dari kejaran kedua kapal perang berat Jerman tersebut dengan dibantu hujan badai serta kabut tebal yang menyelimuti Selat Denmark.
Pada pagi hari tanggal 24 Mei 1941, pukul 05.05 Cuaca sudah agak cerah. Bismarck dan Prinz Eugen tengah berlayar mengarungi Selat Denmark saat para kru "hydrophones" yang bertugas diatas Prinz Eugen mendengar suara baling-baling dari 2 kapal yang tidak dapat diidentifikasi. Meskipun Jaraknya jauh, Kedua kapal "asing" ini berhasil diketahui arah berlayarnya dan ternyata mereka mendekati Bismarck dan Prinz Eugen dengan kecepatan tinggi. Benar saja, Pada pukul 05.45 Para Kru Pengawas dari Anjungan Observasi Bismarck dan Prinz Eugen melihat kepulan asap dari cakrawala. Dengan sigap, Laksamana Lutjens segera memerintahkan awaknya untuk bersiaga menuju stasiun tempur masing-masing. Di lain pihak, Laksamana Lancelot Holland selaku Komandan Armada AL Kerajaan Inggris yang bertugas diatas HMS Hood salah mengira bahwa Armada musuh yang berada di posisi depan adalah Bismarck. Laksamana Holland segera memerintahkan HMS Hood untuk melakukan salvo meriam utamanya ke arah Prinz Eugen yang ia sangka sebagai Bismarck.
