In 1688 zou hij een eiland ontdekt hebben bij Nova Zembla dat hij naar [[Nicolaas Witsen]] noemde. Witsen was erg ingenomen met de vernoeming, maar het eiland bleek een hersenspinsel.<ref>Marion Peters, De wijze koopman, p. 173.</ref> Nog in hetzelfde jaar zou De Vlamingh een tocht maken naar [[Batavia (Nederlands-Indië)|Batavia]].<ref>http://www.nla.gov.au/exhibitions/southland/Char-Willem_de_Vlamingh.html</ref>
De VlamingVlamingh werd in 1696 commandeur over drie schepen waarmee hij, in opdracht van de VOC-[[bewindhebber]]s [[Joan Geelvinck (1644-1707)|Joan Geelvinck]] en Witsen, de westkust van [[Australië (continent)|Australië]] verder in kaart bracht.<ref>Marion Peters, De wijze koopman, Het wereldwijde onderzoek van Nicolaes Witsen (1641-1717), burgemeester en VOC-bewindhebber van Amsterdam, p. 88.</ref> Hij kreeg de opdracht een inwoner van het geheimzinnige [[Terra Australis]] te vangen te zoeken naar het vermiste [[Vereenigde Oostindische Compagnie|VOC]]-schip ''[[Ridderschap van Holland (schip, 1681)|De Ridderschap]]'', dat op 11 juli 1693 uit Nederland was vertrokken naar Batavia; het had 325 man aan boord. Begin 1694 had ''De Ridderschap'' [[Kaap de Goede Hoop]] aangedaan, daarna was het spoorloos verdwenen.
Op 2 of 3 mei 1696 voer De VlamingVlamingh van Texel met het [[fregat]] de ''Geelvinck'', vergezeld door de [[hoeker]] ''Nijptangh'' en het [[galjoot]] '''t Weseltje''. De Vlamingh kreeg uitgebreide instructies mee, waarin ook een paragraaf over [[Tristan da Cunha]] was opgenomen. Hij moest onderzoeken of er een goede ankerplaats was en een goede plaats om aan land te gaan. Ook had hij opdracht het eiland en omliggende eilanden in kaart brengen. Het resultaat was dat de VOC definitief besloot dat Tristan Da Cunha ongeschikt was als verversingsstation op de route naar de Oost.
Bij [[Kaap de Goede Hoop]] bleef het schip langer dan de bedoeling was; de bemanning moest herstellen van [[scheurbuik]]. Er kwam nog een cartograaf aan boord en drie tolken en slaven die Maleis spraken en na een succesvolle tocht zouden worden vrijgelaten. De beoogde schilder bleek reeds vertrokken naar Batavia en de [[predikant]] aan boord kreeg opdracht kustprofielen te maken.
