Artık Sakız adası meselesi, Padişahın zihnini meşgul eden tek mesele idi. Daah önce haftada 2 defa toplanan Divan-ı Hümayun toplantılarını, 4 güne çıkardı ve kendisi de işitrak ediyordu. Bir Cuma günü toplanan Divan'da, gür sesiyle:-Küffar burnumuzun dibine kadar sokuldu. Az kaldı Divanımızı basacak. Gayret-i Diniyye nerede? Himmet-i Vataniyye ne oldu? Şecaat-i İslamiyye bu mudur?Sonra Kaptan-ı Derya Amcazade Hüseyin Paşaya döndü:-Sen ki Kaptan-ı Deryasın. De bakalım tedbir ne ola? Sakız nasıl ele geçer?-Selefimiz Mısırlıoğlu İbrahim Paşa daha münasip tedbir sahibidir Devletlûm..dedi. Padişah bu sefer ona döndü. Kızmadan:-Baka Mısırlıoğlu! Gayri laftan bıktık usandık. Kat'i tedbir isteriz. Ne lazımsa söyle! Seni Veziriazam ve diğer denizciler de methettiler. Bu yüzden Sakız fethine seni Serasker tayin eyledik. Mısırlıoğlu acele etmeye mecburdu. İlk iş olarak, Mezzomorto Hüseyin Paşayı çağırdı. Onu kendisine yardımcı yapacaktı.Hüseyin Paşa, eski Cezayir Beylerbeyi idi. Gençliğinde, Venedik korsanlarıyla çarpışır ken ağır yaralanmış. Düşman onu öldü sanıp bırakmış. Ama bir müddet sonra karşılarında savaşırken görünce, "yarı ölü" manasına gelen :-Mezzo morto, mezzo morto...diye bağırmışlar. Bundan sonra da bütün Akdeniz'de bu isimle anılır olmuş. Hüseyin Paşa sonraları İstanbul'a çağırıldı ve Tuna Kaptanı, Karadeniz Kaptanı, Kalyonlar Kaptanı olarak görevler yaptı. Kaptan-ı Deryanın kendisini çağırdığını duyunca, hemen Kasımpaşa'ya vardı. Mısırlıoğlu, kendisine kısaca durumu anlattı ve hemen hazırlılara başladılar. Nihayet 1695 yılı Ocak ayının ilk günlerinde Donanma-yı Hümayun Beşiktaş'tan hareket etti.Osmanlı donanması 26 Ocak 1695'te İzmir limanına geldi. Bunu haber alan Venedik donanması da hemen, 20 kalyon, 24 çektiri ve altı mavnadan oluşan bir filo ile Sakız limanından hareket ederek, Urla ile Karaburun arasındaki Koyunadaları civarına geldi. Fakat havaların kötü gitmesi yüzünden sekiz gün boyunca her iki donanma da yerlerinden hareket edemediler. 9 Şubat Çarşamba günü Osmanlı donanması, Venedik donanması ile karşı karşıya geldi ve savaş başladı. Daha muharebenin başında, bir Osmanlı kalyonundan atılan mermilerle, yetmişten fazla top ve altı yüz asker taşıyan La Stella kalyonu battı. Onun yardımına gelmek isteyen aynı büyüklükteki Leone del Corranto gemisi de aynı akıbete uğradı. İlk anda iki büyük gemisini kaybeden Amiral Benedetto Gianni Vittorio, birden neye uğradığını şaşırdı ve aleyhine dönen durumu düzeltmek için amiral gemisi ile ileri atıldı, fakat teknesine isabet eden bir gülle ile öldü. Yerine geçen yardımcısı Amiral Contarini ise, Türk saldırısı karşısında acze düştü. Mezzomorto Hüseyin Paşa'nın cesaretle yaptığı manevralar ile zafer bizim oldu. Venediklilerin altı büyük savaş gemisi battı, bir çoğu hasara uğradı ve binlerce askeri denize döküldü. Akşamüzeri savaş tatil edildi ve Venedikliler Koyunadalarına, Osmanlı donanması da Karaburun yakınlarında Eğri limanına çekildi. Burada on gün kadar kaldılar. 18 Ocak 1695 günü Osmanlı donanması, düşmana kesin darbeyi indirmek ve Sakız adasını geri almak için Eğri limanından ayrıldı. Bu sırada Küçük Cafer Paşa, süratli bir gemiyle donanmaya yetişerek, Sultan II. Ahmed'in vefat ettiğini, yerine II. Mustafa'nın geçtiğini haber verdi. Mezzomorto Hüseyin Paşa, yeni padişaha zafer müjdesi götürmeğe yemin etti ve:-"Yâ Rabbi, sen büyüksün, her şeye kâdirsin, düşmanı karşıma çıkar, onu bana göster" diye dua etti. Bu dua kabul olmuş olacak ki, öğleye doğru şiddetli bir rüzgar çıktı. Hızla yol alan kalyonlar, Koyunadaları karşısındaki Kolokitya limanının onbeş mil ötesinde Venedik kalyonları ile karşılaştılar ve hemen hücum ettiler. Savaş öğleye kadar sürdü. Hüseyin Paşa, rüzgarın bütün şiddetine rağmen, denizlere hükmederek dövüşüyordu. Pervasızca ileri atılıyor, düşman hatlarını bozuyor, gemilerde yangınlar çıkarıyordu. Venedikli amiraller ne yapacaklarını şaşırmışlardı. Contarini:-Bu Mezzomorto bir sihirbaz! Diyordu. Hayır, sihirbaz değil, Hüseyin Paşa, uzun yıllar Venediklilerin elinde esir kalmış, onları gayet yakından tanımış ve kurtulduğu gün intikam yemini etmiş tecrübeli bir Türk amirali idi. Contarini kaçmak istiyor, fakat bunu başaramıyordu. Hüseyin Paşa bir an peşlerini bırakmıyordu. Eğer akşam karanlığı imdatlarına yetişmemiş olsa idi, koca donanma en ağır hezimete uğrayacaktı. Batmaktan ve yanmaktan kurtulabilen Venedik gemileri selameti kaçmakta buldular. O kadar korkmuşlardı ki, Sakız adasında daha fazla kalamadılar ve toplarını, araç ve gereçlerini, hatta bir kısım gemilerini bırakarak adadan kaçtılar. Hüseyin Paşa bu zaferi, veziriazama müjdeledi ve adaya derhal asker çıkarılmasını istedi. Derhal adaya hareket eden gemiler, karaya asker çıkardılar ve Sakız adası tek kurşun atılmadan teslim oldu. 22 Şubat 1695 günü kaleye tekrar Türk bayrağını çeken Hüseyin Paşa sevinç gözyaşları döküyordu. Böylece beş ay sonra, kaybettiğimiz Sakız adasını geri aldık.