İnebahtı felaketinde Osmanlı donanması, Haçlı donanması tarafından pusuya düşürülüp imha edildiği sırada, Uluç Ali Paşa, kendi kumandasındaki birkaç gemiyi kurtarmayı başarmış ve İstanbul'a gelerek bu faciayı haber vermişti. Bunun üzerine Sultan II. Selim Han onun bu kısmi başarısından dolayı onu Kaptan-ı Deryalığa tayin etti ve adını da Uluç Ali Reis'den Kılıç Ali Paşa'ya çevirdi.
Diğer taraftan Sadrazam Sokollu Mehmed Paşa, yeniden donanma inşası için, bütün devlet erkanını harekete geçirerek, Osmanlı ülkelerinin bütün imkanlarını seferber etmişti. Çalışmaları büyük bir titizlikle takibediyor, heryere girip çıkıyor ve işlerin aksamasına meydan vermiyordu. Yanına Kaptanı Derya tayin edilen Kılıç Ali Paşa'yı da alarak çıkıyordu.
Kılıç Ali Paşa bu çalışmaları hayretle takibediyordu. Kendisi leventlikten yetişme olduğu için, bütün hayatı denizlerde geçtiğinden ve İstanbul'un ahvalini, devletin kudret ve imkanları hakkında faza bir bilgi sahibi olamadığından, bir gün Sokollu'ya:
-Tekne icad ve ihdası mümkündür. Velakin bir kış içinde ikiyüz gemiye beş altı yüz lenger ve buna göre âlât ki, palamar ve ip ve her gemiye yelken asla tekmil ve tedarik olunma sına ihtimal yoktur.
Bu sözleri işiten Sokollu Memed Paşa öfkelenerek:
-Paşa, Paşa... sen bu Devlet-i Aliyye'yi henüz tanımamışsın. Bu devlet öyle bir devlettir ki, murad edinirse, cümle donanmanın direklerini altından, lengerlerini gümüşten, iplerini ibrişimden ve yelkenlerini atlastan etmekte güçlük çekmez. Gemilerin mutad olan aletlerini ve yelkenlerini yetiştiremez isem, gel benden al...
Bu söz üzerine hatasını anlayan Kılıç Ali Paşa, Sokollu'nun elini öptükten sonra:
-Tahkîk bildim ki, bu donanmayı siz tekmil edersiniz...dedi.
Beş buçuk ay sonra...
Osmanlı devletinin muazzam imkanlarıyla, tam İKİYÜZELLİ gemi, bütün teçhizatı, müthiş silahları ve cephanesiyle harbe hazır olarak, Kılıç Ali Paşa'nın kumandasında, 12 Haziran 1572 Perşembe günü, Hristiyan dünyasının hayretleri altında Akdeniz'e açıldı ve bir asır daha bu suları bir Osmanlı gölü halinde tuttu.
