Cornelius Houtman, jolle yrityksen johto uskottiin, oli ollut monta vuotta Portugalin palveluksessa, tehnyt Itä-Intiaan monta matkaa ja tunsi siis väylät ja paikat. Väyläoppaana hänellä oli kerallaan Jan van Linschotenin (II, s. 445) kirjoittama »Navigatio ac itinerarium», joka perustui tekijän omiin ja muidenkin matkustajain havaintoihin. Houtman suuntasi ensinnä Madagaskariin ja poikkesi sitten Etu-Intiaan, mutta kun portugalilaiset joka paikassa häntä ahdistivat, niin hän lopulta päätti purjehtia Javaan, jonka rikkaus oli hänelle tunnettu ja jossa portugalilaisilla oli verraten vähän sananvaltaa. Mutta portugalilaiset seurasivat sinnekin ja yllyttivät asukkaita häntä vastaan. Houtman koetti saada kuormat Bantamista, nykyisin raunioiksi sortuneesta kaupungista, joka siihen aikaan oli pippurikaupan keskusta Javassa, mutta portugalilaiset saivat kun saivatkin tämän juonillaan estetyksi, ja Houtmanin täytyi purjehtia edelleen. Vasta Javan itärannalla hollantilainen laivue saattoi rauhassa virkistää voimiaan. Paluumatka tapahtui pitkin Javan etelärantaa, jonka väyliä nyt ensi kerran kyntivät eurooppalaiset laivat. Taisteluitten ja muitten vastoinkäymisten kautta Houtman oli menettänyt kaksi laivaansa ja kaksi kolmannesta miehistään, mutta siitä huolimatta varustajat päättivät tämän kaupan kannattavan, jos sitä käytiin riittävillä voimilla. Kotiin tuoduista merkillisistä esineistä mainittakoon kamelikurjen näköinen kasuaari, joka lienee Javaan tuotu Ceramista tai Papuain saarilta.
Retkiä Magalhãesin salmen kautta.
Yhdistettyjen Alamaitten satamat alkoivat tämän jälkeen kilvan lähettää laivastoja Itä-Intiaan. Toiset purjehtivat tavallista tietä Hyväntoivonniemen ympäri, toiset yrittivät päästä sinne länsitietä. V. 1598 lähti ensimmäinen laivue Magalhãesin salmen kautta. Ainoastaan yksi viidestä pääsi Molukeille, ja sen portugalilaiset anastivat. Erään toisen valtasivat espanjalaiset Perussa, kolmas palasi väliltä kotia. Pari laivaa suuntasi muista myrskyssä erottuaan Japaniin, jonne toinen lopulta saapuikin, vaikka niin huonossa kunnossa, että miehistö tuskin kykeni purjehdusta hoitamaan. Laivaa johti englantilainen luotsi William Adams, kapteenin saatua surmansa kahakassa Chilen rannikolla. Adams pääsi shogunin (Japanin sijaishallitsijan) suosioon, mutta maasta häntä ei laskettu. Hän sai Japanissa tiluksia ja otti japanilaisen vaimon. Kun kapteeni John Saris v. 1613 saapui Japaniin, niin Adams sai luvan palata kotimaahansa, mutta ei enää sitä lupaa käyttänyt, vaan rupesi englantilaisen Itä-Intian komppanian asiamieheksi. Matkoja hän kuitenkin teki sekä Siamiin että Kotshinkiinaan. Hänen japanilainen nimensä oli Anjin Sama. Eräs Jedon kaduista on saanut hänestä nimensä, jota paitsi japanilaiset joka vuosi kesäk. 15 p. juhlivat hänen muistoaan.
Parempi onni oli Olivier Van Noortilla, joka syysk. 1598 lähti
Rotterdamista neljällä laivalla, Magalhãesin salmen kautta hänkin.
Anastettuaan yhden espanjalaisen laivan Chilen rannalla ja toisen
Filippinien luona hän saapui Borneon Bruneihin ja palasi Sundasalmen
kautta ja Hyväntoivonniemen ympäri, saapuen Hollantiin elokuussa 1601.
Hän oli ensimmäinen hollantilainen kapteeni, joka purjehti maan ympäri.
Vuonna 1598 Amsterdamin kauppiaat lähettivät kahdeksan laivaa amiraali J. van Neckin johdolla perustamaan vakinaisen kauppa-aseman Javaan, jonka he päättivät ottaa toimiensa tukipaikaksi Itä-Intiassa. Van Neck purjehti Hyväntoivonniemen ympäri ja pääsi onnellisesti Javaan, jossa laivoista neljä otti täydet maustekuormat. Itse hän jatkoi neljällä laivalla Molukeille, karkoitti siellä Portugalilaiset muutamilta asemilta ja teki ruhtinaitten kanssa kauppaliittoja. Otettuaan lopuksi täydet maustelastit hän palasi kaikkine laivoineen onnellisesti kotimaahan. Osa van Neckin laivastosta poikkesi Mauritiukseen, joka oli asumaton, ja istutti sinne puutarhan.
Hollantilainen Itä-Intian komppania.
Tämä onnistunut matka kiihoitti kauppiaita kaikin voimin jatkamaan tuottavaa kauppaa ja 1601 lähetettiin Itä-Intiaan neljäkymmentä laivaa, jotka kaikki palasivat täysin kuormin. Mutta kun oli pelättävää, että keskenäinen kilpailu estäisi tätä kauppaa kaikin puolin edullisesti kehittymästä, niin Itä-Intian kauppa kenraalistaattien välityksellä annettiin yhdelle ainoalle suurelle seuralle, kuululle »Itä-Intian kauppaseuralle», joka perustettiin maaliskuussa 1602 ja sai sekä valtion että koko kansan kannatuksen. Seura sai mitä laajimmat oikeudet, yksinomaisen oikeuden kaupan käyntiin Itä-Intiassa, oikeuden nimittää sinne virkamiehiä, käydä sotaa ja tehdä rauhan, solmia liittoja, leimata rahaa, rakentaa kaupungeita ja linnoja, kaikki kenraalistaattien nimessä. Seuraan liittyivät kaikki pienemmät kauppaseurat. Sen pääoma, 6.600.000 guldenia, oli ajan oloihin nähden suunnattoman suuri, kaksi vertaa suurempi kuin kaksi vuotta aikaisemmin perustetun englantilaisen Itä-Intian komppanian. Mutta liike ja toimeliaisuus olivatkin kasvaneet Yhdistyneitten Alankomaitten satamissa suunnattomasti. Grotiuksen tietojen mukaan rakennettiin niissä vuoden 1600 vaiheilla 2000 laivaa.
Hollantilaisen Itä-Intian komppanian lähettämään ensimmäiseen laivastoon kuului 13 alusta, ja sitä komensi van der Hagen. Kun hän oli Javan Bantamissa pippurikuormaa ottamassa, niin saapui sinne Amboinasta lähetystö pyytämään apua portugalilaisia vastaan. Van der Hagen mielihyvällä noudatti kutsumusta ja sitkeän vastarinnan jälkeen Amboinan portugalilainen linna valloitettiin. Se sai nyt nimeksi Victoria, ja siitä tuli hollantilaisten ensimmäinen tukikohta Aasiassa. Amboinasta käsin he vähitellen valloittivat muutkin Molukit linnoineen, Tidoria ja Ternatea lukuunottamatta, joissa espanjalaiset pitivät jonkun aikaa puoliaan.
Englantilaisten retkiä Itä-Intiaan.
Hollantilaisten koroitettua v. 1599 pippurin hinnan 3 shillingistä 6 ja 8 shillinkiin naulalta englantilaiset alkoivat täydellä todella ajatella Intian kauppaa. V. 1600 perustettiin englantilainen Itä-Intian komppania, siis paria vuotta aikaisemmin kuin hollantilainen. Neljä suurta laivaa lähetettiin v. 1601 matkaan, John Davis luotsina. Tällä retkellä huomattiin, että sitrunamehu oli mitä paras keino keripukkia vastaan. Laivasto löysi Chagos-saaret Intian meren keskeltä ja saapui sitten Nikobarien kautta Atjehiin, Sumatran rannalle, josta saatiin vähän pippuria. Lisää samaa haluttua tavaraa saatiin Javan Bantamista. Malakan salmessa anastettiin Portugalin lipulla purjehtiva kauppalaiva. Kovia myrskyjä paluumatkalla kestettyään laivasto syksyllä 1603 saapui kotiin täysin kuormin. V. 1605 lähetettiin uusi laivasto, joka toivoi saavansa tehdä vapaasti kauppaa, kun Englanti oli tehnyt Portugalin ja Espanjan kanssa rauhan, mutta hollantilaiset kävivät sotaa edelleenkin, valloittivat paraillaan toisen portugalilaisen aseman toisensa jälkeen, ja minne englantilaiset tulivatkin, kaikkialla tämä sota ja hollantilaisten kateus haittasivat heidän kauppaansa. Yksi laiva matkalla menetettiin. Kapteeni Middleton, joka tätä retkikuntaa johti, sai kuitenkin Molukeilta neilikoita, ja tästä hänet lyötiin ritariksi. V. 1607 lähetettiin jälleen kolme laivaa, jotka kulkivat toisia teitä, Sokotran ja Adenin kautta Suratiin, Etu-Intian länsirannalle. Englantilaiset koettivat sieltä käsin päästä suuren mogulin kanssa yhteyteen ja lähettivät Suratista erään kapteenin Jehangirin hoviin, jossa hän sai paljon arvokkaita tietoja Intian oloista. Matkoja alettiin sitten tehdä yhä taajemmin ja seitsemännellä matkalla, v. 1611, komppanian laivat kävivät aina Siamissa saakka, perustaen silloiseen pääkaupunkiin Ajuthiaan kauppa-aseman.