Laksamana Malahayati dan pasukan Inong Balee telah menunggu dan bersiaga. Sultan pun memerintahkan Laksamana Malahayati mengusir dua kapal Belanda tersebut. Pertempuran di tengah laut tak terelakkan. Pasukan Inong Balee berhasil menghancurkan dua kapal dagang itu. Dalam sebuah duel satu lawan satu di atas kapal musuh pada 11 September 1599, Laksamana Malahayati berhadapan dengan Cornelis. Nyawa Cornelis pun melayang di ujung rencong Malahayati.
Seperti dikisahkan sejarawan Marie van C Zeggelan lewat bukunya Oude Glorie yang terbit pada 1935, Belanda disebutkan banyak kehilangan pasukan mereka, dan sebagian yang masih hidup termasuk Frederik de Houtman dijebloskan ke hotel prodeo alias penjara.
Tak hanya cakap sebagai panglima perang di lautan, Malahayati juga dikenal sebagai juru runding yang piawai. Pemerintah Belanda mengajukan pembebasan para tawanan perang mereka yang ditahan pihak Kesultanan Aceh termasuk Frederik de Houtman. Sultan pun mengutus Malahayati untuk maju ke meja perundingan menghadapi Belanda. Sebuah syarat pun diajukannya, yaitu Belanda harus membayar ganti rugi atas peperangan yang mereka timbulkan demi membebaskan prajurit-prajurit yang dipenjara.
Malahayati juga dipercaya menerima utusan khusus Ratu Elizabeth I bernama James Lancaster yang juga seorang saudagar dagang besar pada masanya. Lancaster mengunjungi Aceh pada 5 Juni 1602 memakai kapalnya, Red Dragon. Ia mengutarakan maksud kepada Malahayati untuk membeli rempah-rempah Aceh, seperti halnya saat mengunjungi Maluku dan Banten. Misi itu berlangsung sukses karena Malahayati setuju dengan tawaran yang disampaikan Lancaster bahwa mereka hanya ingin berdagang dan bukan berperang.
