Osmanlı İmparatorluğu'nun Ege denizi ve Akdeniz'de genişlemesi arttıkça Venedik'in etki alanı daralıyordu. Bundan dolayı Venedik, sürekli olarak Osmanlı'nın aleyhine çeşitli ittifaklar kuruyor, Osmanlı'nın düşmanlarına yardım ediyordu. En son, kendilerine gönderilen bir elçi heyetinin gemisini batırmış, gemidekilerin hepsini kılıçtan geçirmişlerdi.
Yapılan istişareler sonucu Venedik üzerine bir ordu gönderilmesi kararlaştırıldı. Donanma kuvvetlerine Barbaros Hayreddin Paşa, kara kuvvetlerine de Lütfi Paşa komuta edecekti. Ordu, donanmayla birlikte, 1537 Mayıs'ında İstanbul'dan hareket etti. Sinan, Lütfi Paşa'nın maiyetinde bir savaşa daha katılıyordu.
Osmanlı ordusu, 23 Temmuz 1537'de İtalya'nın Pulya şehrine çıktı. Lütfi Paşa, Otranto ve civarını ele geçirdi.

Buradan Korfu adasına hareket edildi. 25 Ağustos'ta Korfu'ya çıkarma yapıldı. Yaklaşık yirmi gün süren kuşatma, kış mevsiminin başlayacak olması dolayısıyla kaldırıldı.
Osmanlı ordusu İtalya seferinden döndükten sonra, Barbaros Hayreddin Paşa, 1538 kış ve baharını İstanbul'da geçirdi. Yaz günleri geldiğinde tekrar denize açıldı. Kanuni Sultan Süleyman, bundan bir ay sonra Kara Boğ-dan seferine çıktı.
II. Beyazıd zamanından beri Osmanlı'ya bağlı Kara Boğdan'da (Moldavya) hiç sorun çıkmazdı. Fakat son zamanlarda Kara Boğdanlılara bir şeyler oluyordu. Ya bir şeyi bahane edip mesele çıkarıyorlardı, ya da mesele çıkarmak için hiçbir fırsatı kaçırmıyorlardı. Kah Osmanlı'nın düşmanlarıyla açık ittifaklara giriyorlar, kah Osmanlı'nın kendisine dost bellediği insanlara saldırıyorlardı. Bu durumda Kara Boğdan üzerine bir sefer kaçınılmazdı. Öyle de oldu.
Kanuni Sultan Süleyman, istişarelerden sonra orduya hazır olması emrini verdi ve İstanbul'dan yola çıkıp hızlıca Edirne'ye vardığında, kendisini bekleyen orduya, "Seferimiz Boğdan üzerinedir!" diye buyurdu.
Ordu, yaptığı birçok seferde olduğu gibi, hiçbir direnişle karşılaşmadan ilerliyordu. Osmanlı ordusu Prut Nehri'ne vardı ve burada orduyu doğal bir zorunluluk durdurdu; ordu, tıpkı Van Gölü'nde olduğu gibi doğal bir engelle karşılaşmıştı. Orada gemi, burada köprü yoktu.

Ordunun Prut Nehri'ni geçmesi. Kara Boğdan içlerine doğru ilerlemesi gerekiyordu. Durmaya gelmezdi. Derhal bu işlede ilgilenen mimarlar, işçiler çalışmaya başladılar.
Nice mimar, nehir üzerine bir köprü kurmak için didiniyordu; herkeste bir telaş, bir telaş. Fakat ne çare! Kurulan her köprü kolayca, kartondan yapılmış gibi yıkılıveriyordu. Peki, koca Osmanlı ordusunda bir köprü kuracak denli iyi bir mimar yok muydu da kurulan köprüler birbiri ardına, kartondanmış gibi yıkılıveriyordu? Hayır, elbette öyle değil! Lakin mimarların köprü kurmaya uğraştıkları yer, bir bataklıktı. Balçık ve bataklığın üzerine yıkılmayacak bir köprü kurmak için uğraşıyordu ordunun mimarları. Üstelik kuracakları köprü haddinden fazla sağlam olmalıydı; çünkü köprüden koca bir ordu geçecekti.
Peki biraz ilerisi kuru değil miydi? Değildi. Peki biraz ilerisi? Değildi. Hem ordunun, durup köprü kurmak için kuru toprak aramaya vakti de yoktu. Köprü ordunun olduğu yere ve vakit geçirilmeden kurulmalıydı; fakat nasıl? Herkesin aklındaki tek soru buydu.
Mimarları, onlara nezaret eden vezirleri bir şaşkınlık almıştı. Bataklık araziye kurulan köprülerin birbiri ardınca yıkılıp durması herkesi çileden çıkarıyordu. Canla başla çalışanlara bakıp bakıp "Bu iş olmayacak!" deyip dururken Lütfi Paşa'nın aklına Mimar Sinan geldi. "Bu işi yapsa yapsa Sinan Subaşı yapar!" dedi.
Lütfi Paşa derhal Kanuni Sultan Süleyman'ın huzuruna çıktı. "Saadetli padişahım! Bu köprünün yapımı, Sinan Subaşı denilen kulunuzun becerisiyle gerçekleşebilir," dedi.

Kanuni Sultan Süleyman, "Kimdir Sinan Subaşı?" dedi.
Lütfi Paşa, "Kendisi haseki kulunuzdur. Emir buyurun, meslektaşlarıyla birlikte bu işe o baksın!"
Kanuni Sultan Süleyman, "Ordudaki mimarların yapamadığını yapabilir mi?"
Lütfi Paşa, "Kendisi çok tanınmış bir ustadır! Maharetli bir mimardır!"
Kanuni Sultan Süleyman, hiç duraksamadan, "Tez baksın!" emrini verdi.
Lütfi Paşa, adam salıp Sinan'ı buldurdu. Kanuni Sultan Süleyman'ın huzuruna çıkardı.
Kanuni Sultan Süleyman, "Ne dersin Sinan Subaşı? Bu köprüyü kurabilir misin?"
Sinan, "Sultanımın emri, Allah'ın yardımıyla gerçekleşir!" dedi. Kanuni Sultan Süleyman da "Durma öyleyse!" dedi Sinan'a.
Huzurdan çıktıklarında Lütfi Paşa Sinan'a, "Haydi! Göreyim seni! Yüzümüzü kara çıkarma! Bizi mahcup eyleme!" dedi.
Sinan emrindeki mimarlar ve işçilerle derhal çalışmaya başladı. Hummalı bir çalışmadan sonra on üç günde köprüyü kurdu.
Sağlam mı_ sağlamdı kurduğu köprü. Öyle hiç balçık, bataklık üzerinde kurulmuş gibi değildi. Çok sağlam bir zemin üzerine kurulmuş, ne yaparsan yap göçmez bir köprüydü.


İslam ordusu ve şahlar şahı Kanuni Sultan Süleyman, Sinan'ın kurduğu köprüden büyük bir sevinçle geçti. Ordunun yine mühim bir müşkülü halledilmişti.
Ordu karşı kıyıya geçerken öyle bir seviniyordu ki Lütfi Paşa. Neredeyse sevincinden yerinde duramıyordu. "Bu Sinan yok mu, bu Sinan!" diyordu da başka bir şey demiyordu.
İşte kurulan köprü çok hoşuna gitmişti Lütfi Paşa'nın. Âdeta sevincini dizginleyemediği için, hızını alamayıp "Bu köprüyü biz gittikten sonra kafir yıkmasın diye, yanı başına bir kule yapıp koruyalım," dedi. "Kuleye birkaç asker bırakıp bu köprüyü koruyalım," dedi.
O sırada yanlarında bulunan Vezir-i Azam Ayaş Paşa Sinan'a dönerek, "Sen ne dersin bu işe?" dedi. Sinan'ın biraz duraklaması üzerine, "Kule yapma fikrine ne dersin?" diyerek sorusunu yeniledi.
Sinan, "Uygun değildir," dedi.
Doğrusu bu cevap cesur bir cevaptı. Durup dururken bir vezire karşı çıkıyordu, hem de kendisini çok seven bir vezire.
Lütfi Paşa, Sinan'dan böyle bir cevap beklemiyordu; Ayaş Paşa'ysa beğenmişti Sinan'ın cevabını. "Aklın yolu bir değil mi?" demişti kendi kendine. Cevabın daha iyi anlaşılması için Sinan'a, "Neden uygun değildir?" dedi Ayaş Paşa.
Sinan, "Çünkü kafir, biz gittikten sonra çaba gösterip birkaç kişiyle bu kuleyi ele geçirebilir."

Ayas Paşa, "Ele geçirsin?"
Sinan, "O zaman adı bir kale fethetmişe çıkar kafirin."
Ayas Paşa, "Peki ne yapalım?"
Sinan, "Belki bu köprüye bir değer vermek doğru değildir. Padişahımızın ülkesinde nerede bir köprü yapmak gerekirse, orada hemen bir köprü yapılması mümkündür."
Gücenmişti Lütfi Paşa Sinan'ın bu sözlerine. Kızgın bir ses tonuyla, "Senin korkun burada inşa edilecek kalede komutan olarak kalmaktır!" dedi. Böyle derken Sinan'a, bir zamanlar Van Gölü'nde kendi inşa ettiği gemilere yine kendisinin kaptanlık yapmasını hatırlatıyordu. "Şimdi de kurduğun bu güzel ve stratejik köprüyü sen koru bakalım, dememizden korkuyorsun, değil mi?" demeye getiriyordu Lütfi Paşa.
Böyle bir ihtimalden korkmasına korkuyordu Sinan ya, ne desindi? Hem pişman olmuştu kendisini çok seven bir veziri gücendirdiği için. Fakat insan konuşacaksa sözün doğrusunu söylemeliydi.
Lütfi Paşa'nın, "Senin korkun kalede komutan olarak kalmaktır!" demesi üzerine Sinan, yıllar sonra, Lütfi Paşa'ya, Prut Nehri'nin üzerine kurduğu köprünün başında şöyle dediğini bildirecekti:

"Padişahın eski kölesiyiz Kale korumasının da eriyiz
Eskiden beri kulu ve yeniçerisiyiz
Uğrunda semender gibi ateşe girip yanarız."

Lütfi Paşa'ya, "Kule yapılır ve emir buyurursanız, korumak için burada kalırım," demişti Sinan.
Sinan'ın orada kaldığını bir düşünsenize! Basit bir köprü için. Kara Boğdan'da, kuş uçmaz kervan geçmez bir yerde bir kuleyi bekleyecekti bütün ömrünce! Peki o zaman Süleymaniye'yi kim yapacaktı?
Lütfi Paşa, Sinan'ın verdiği cevaptan tatmin olmamıştı. Cevap çok mantıklıydı; ama bir vezir gururu da vardı işin içinde. O ara, köprüden Rumelili askerlerin geçişine nezaret eden Sofu Mehmed Paşa'yı gördü Lütfi Paşa. Emir verip yanına gelmesini istedi. "Hele, o da gelsin.!" dedi kızgınca, neredeyse bağırarak.
Sofu Mehmed Paşa, sözüne itibar edilen bir paşaydı. Akıllı ve ileri görüşlüydü. Lütfi Paşa, onu bu özelliklerinden dolayı çağırtmıştı.
Yanında, birkaç subayla gelen Sofu Mehmed Paşa'ya, "Bu köprü bizce çok kıymetlidir. Buraya bir kule yapıp onu korumaya ne dersin?" dediğinde Sofu Mehmed Paşa, "Eskiden Osmanlılar Rumeli'ye geçtikleri zaman gemilerini yakmışlardı. Bizim bu köprüyü kendimizin yıkması lazım gelirken, kule yapıp korumaya kalkışmak, kaçkınlarımıza sığınak hazırlamaktır!" dedi.
Sofu Mehmed Paşa da aynı şeyleri söyleyince, tartışma biraz alevlenir gibi olduysa da, Vezir-i Azam Müşir Ayas Paşa ve yanındakiler, Lütfi Paşa'yı kule yapıp köprüyü korumak fikrinden vazgeçirdiler.
Sinan, her ne kadar, Lütfi Paşa'yı gücendirdiği için pişmanlık duyduysa da doğruyu söylediği için mutluydu. Haklı çıktığı için mutluydu. Bu olay Sinan'ın iyi bir asker, iyi bir mimar olmasının yanında hem doğru sözlülüğünü, hem de ileri görüşlülüğünü gösteriyordu.
Ordu kazasız belasız nehri geçmiş ve Kara Boğdan'da ilerlemeye başlamıştı. İlerliyordu ilerlemesine ya karşısına bir başka ordunun çıktığı filan yoktu. Çoğu zaman böyle olurdu. O zamanlar Osmanlı'nın gücünün karşısına bir güç, ordusunun karşısına bir ordu koyacak devlet yoktu. Kara Boğdan voyvodası, kendi topraklarında ilerleyen Osmanlı ordusunun karşısına çıkamadı. Osmanlılar varıp Kara Boğdan'nın merkezi Suceva şehrine girdiklerinde, takvimler 16 Eylül 1538'i gösteriyordu.
Kanuni Sultan Süleyman ertesi gün, Kara Boğdan'ın beylerini, valilerini, ileri gelenlerini topladı ve kendisine düşmanlık eden Kara Boğdan voyvodasını görevden aldığını, kendilerine yeni bir voyvoda seçmeleri gerektiğini söyledi. Kara Boğdanlılar kendilerine yeni bir voyvoda seçtiler. Emir krallar kralından geliyordu çünkü.