W tym samym czasie do Amsterdamu wrócił z Goa Jan Huygen van Linschoten, który skopiował, a następnie opublikował portugalskie tajne portolany (mapy nawigacyjne) oraz informacje o trasie morskiej do Indii wokół Przylądka Dobrej Nadziei i o warunkach żeglugi na Oceanie Indyjskim, opisując szczegółowo przebieg prądów morskich, rozmieszczenie głębin i mielizn, układy wiatrów, pory monsunów itd. Na podstawie informacji zdobytych przez de Houtmanów i van Linschotena kupcy amsterdamscy zorganizowali wyprawę do Bantam, głównego portu obrotu pieprzem w Indiach Wschodnich. W 1594 kupcy założyli Kompanię van Verre (hol. Compagnie van Verre), a 2 kwietnia 1595 Amsterdam opuściły cztery statki pod dowództwem Cornelisa de Houtmana: Amsterdam, Hollandia, Mauritius i Duyfken.
Żeglarze natrafili na trudności już na początku wyprawy. Wielu uczestników ekspedycji zachorowało na szkorbut z powodu niewystarczających racji żywnościowych i niedoboru witaminy C. De Houtman zdecydował się zrobić przerwę i uzupełnić zapasy na Madagaskarze. Zatoka, w której kotwiczyły statki holenderskie, znana jest obecnie jako Cmentarz Holendrów (hol. Hollantsche Kerckhoff). W tym samym czasie De Houtman popadł w konflikt ze swoim asystentem Gerritem van Beuninghenem, którego uwięził. Doprowadziło to do kilkumiesięcznego konfliktu z załogą.