Op 2 April 1595 vertrek vier skepe uit Nederland (Mauritius, Amsterdam, Hollandia en Duifje) onder bevel van Cornelis de Houtman. Die vaart word gefinansier deur die Compagnie van Verre. Hul opdrag was om die Soendastraat tussen Java en Soematra te bereik en om soveel inligting moontlik in te samel. Om hierdie handelsroete te vestig moes hulle egter ook die twee belangrike waterbronne aan die suidpunt van Afrika besoek: Sao Bras (later Mosselbaai) en Saldanha. ’n Nederlander, Joris van Spilbergen sou in 1601 Saldanha se naam verander na Tafelbaai.
Na De Houtman het verskeie Nederlandse vlote van verskillende mededingende maatskappye hier aangedoen onderweg na Indië. Dit het so voortgeduur tot in 1602.
In 1602 het die verskillende Nederlandse maatskappye verenig in een groot federasie, die Verenigde Nederlandse Geoktrooieerde Oos-Indiese Kompanjie. Die Kompanjie is bestuur deur die Here XVII, ’n raad van 17 bewindhebbers. Die State-Generaal van Nederland het aan hierdie maatskappy die reg gegee om die soewereine gesag te wees van enige oorsese grondgebiede wat hulle sou annekseer.
Later skryf Jan Pieterzoon Coen ’n pleidooi vir die vestiging van ’n Nederlandse kolonie aan die Kaap. Coen was ’n kampvegter teen Engelse bewind in die Ooste. Die skrywe word egter geïgnoreer.
Dit is eers na die stranding van De Nieuwe Haarlem dat die Kompanjie met nuwe erns na die Kaap begin kyk.