Pada tahun 1592 Cornelis de Houtman dikirim oleh para pedagang Amsterdam ke Lisboa untuk menemukan sebanyak mungkin informasi mengenai Kepulauan Rempah-Rempah. Pada saat de Houtman kembali ke Amsterdam, Jan Huyghen van Linschoten juga kembali dari India. Para pedagang tersebut memastikan bahwa Banten merupakan tempat yang paling tepat untuk membeli rempah-rempah. Pada 1594, mereka mendirikan Compagnie van Verre [nl] (yang berarti "perusahaan jarak jauh"), dan pada 2 April1595 empat buah kapal meninggalkan Amsterdam: Amsterdam, Hollandia, Mauritius dan Duyfken.
Perjalanannya dipenuhi masalah sejak awal. Penyakit seriawan merebak hanya beberapa minggu setelah pelayaran dimulai akibat kurangnya makanan. Pertengkaran di antara para kapten kapal dan para pedagang menyebabkan beberapa orang terbunuh atau dipenjara di atas kapal. Di Madagaskar, di mana sebuah perhentian sesaat direncanakan, masalah lebih lanjut menyebabkan kematian lagi, dan kapal-kapalnya bertahan di sana selama enam bulan. (Teluk di Madagaskar tempat mereka berhenti kini dikenal sebagai "Kuburan Belanda").
Tiba di Jawa
Pada 27 Juni1596, ekspedisi de Houtman tiba di Banten. Hanya 249 orang yang tersisa dari pelayaran awal. Penerimaan penduduk awalnya bersahabat, tetapi setelah beberapa tabiat kasar yang ditunjukkan awak kapal Belanda, Sultan Banten, bersama dengan petugas Portugis di Banten, mengusir kapal Belanda tersebut.
Ekspedisi de Houtman berlanjut ke utara pantai Jawa. Kapalnya takluk ke pembajak. Beberapa tabiat buruk berujung ke salah pengertian dan kekerasan di Madura: seorang pangeran di Madura terbunuh, beberapa awak kapal Belanda ditangkap dan ditahan sehingga de Houtman membayar denda untuk melepaskannya.
Kapal-kapal tersebut lalu berlayar ke Bali, dan bertemu dengan raja Bali. Mereka akhirnya berhasil memperoleh beberapa pot merica pada 26 Februari1597. Kapal-kapal Portugis melarang mereka mengisi persediaan air dan bahan-bahan di St. Helena. Dari 249 awak, hanya 87 yang berhasil kembali. Cornelis de Houtman tewas dalam perjalanan keduanya di atas geladak kapal di Aceh saat pertempuran dengan pasukan Inong Balee yang dipimpin Malahayati tanggal 11 September1599 dalam pertempuran satu lawan satu dengan Malahayati.
Meski perjalanan ini bisa dibilang gagal, ini juga dapat dianggap sebagai semacam kemenangan bagi Belanda. Pihak Belanda sejak saat itu mulai berlayar untuk berdagang ke Timur. Dalam lima tahun kemudian, 65 kapal Belanda telah berlayar ke wilayah tersebut dan bisa disebut memulai penjajahan Hindia Belanda.