In augustus 1642 vertrok Abel Tasman van Batavia met twee schepen onder zijn leiding, de Zeehaen en de Heemskerck. Zijn expeditie zou leiden tot de eerste Europese contacten met de bevolking van Nieuw Zeeland en Tonga en tot het ontdekken van het eiland Tasmanië ten zuiden van Australië. Tasman had verschillende opdrachten meegekregen. Ten eerste moest hij veel verder zuidelijk zeilen dan tot dan toe geprobeerd was en in oostelijke richting op zoek gaan naar het zogeheten onbekende Zuidland (Terra Australis). De VOC wilde weten hoe groot dit continent was, dat ergens zou moeten liggen ten zuidoosten van de Indische archipel. Men hoopte dat dit continent rijk zou zijn aan goud, zilver en handelsmogelijkheden. Eigentijdse kaarten toonden al delen van wat we nu kennen als het continent Australië. Maar men wist niet zeker of deze stukjes land behoorden tot het Zuidland, waarvan men dacht dat het veel groter was dan Australië. Verder wilde de VOC een vaarroute ontdekken om via de Stille Oceaan Chili te bereiken, dat destijds een Spaanse kolonie was. Spanje en Nederland waren destijds nog in oorlog met elkaar en de VOC hoopte Spaanse bezittingen in Zuid-Amerika aan te kunnen vallen. Ten slotte moest Tasman antwoord vinden op de belangrijke vraag of Nieuw Guinea en het Zuidland aan elkaar verbonden waren.
Tasman zeilde eerst naar Mauritius om voorraden te bezorgen voor de Nederlandse post op dat eiland. Vanaf Mauritius vertrokken de Zeehaen en Heemskerck vervolgens in zuidoostelijke richting. Het weer werd gaandeweg erg slecht. De expeditie besloot dan ook een noordelijker koers aan te houden dan de instructies die zij mee had gekregen. Terwijl men eind november oostwaarts zeilde ten zuiden van Australië kwam men een nieuw eiland tegen, dat zij Van Diemensland noemden naar de gouverneur-generaal van de VOC, Anthony van Diemen. Later zou dit hernoemd worden naar Tasmanië. Ondanks het zien van tekenen van leven lukte het de bemanning niet om contact te maken met de bevolking van het eiland.
De expeditie zeilde verder en stuitte halverwege december weer op land. Op 18 december ging de expeditie voor anker in de Golden Bay van het Nieuw-Zeelandse Zuidereiland. Hier vond de volgende dag door een misverstand een bloedig treffen plaats met de Maori die hier leefden. Hierin verloor een aantal bemanningsleden het leven. De expeditie zeilde verder en passeerde in de Straat Cook de doorgang tussen het Noordereiland en Zuidereiland zonder deze te ontdekken. Na vervolgens langs de westkust van het Noordeneiland te zeilen dacht Tasman op 8 januari een stroming te ontdekken die men richting de Stille Oceaan naar Chili zou kunnen brengen. Maar dit kon alleen op basis van zijn observaties niet worden bevestigd.
De expeditie vervolgde de reis in noordoostelijke richting en kwam vervolgens verschillende eilanden tegen van de Tonga-archipel. Ze ging eind januari voor anker bij Tongatapu, het grootste eiland, en Nomuka. Hier was de ontmoeting met de bevolking veel vriendelijker. Na het uitwisselen van geschenken en het inslaan van vers voedsel en drinkwater zeilde Tasman noordwaarts en toen naar het westen. De expeditie passeerde de Fiji-archipel, de Solomon-eilanden en zeilde vervolgens langs de noordkust van Nieuw-Guinea. Van daaruit bereikte men Seram, waar besloten werd om af te zien van de opdracht om de mogelijke verbinding tussen Australië en Nieuw Guinea te onderzoeken. Op 15 juni 1643 keerde de expeditie weer terug in Batavia. De expeditie had enkele nieuwe eilanden ontdekt, maar had de notie dat Australië deel was van een immens zuidelijk continent weerlegd, de verwachtingen daar enorme rijkdommen te gaan aantreffen teleurgesteld, en geen duidelijke antwoorden opgeleverd op enkele andere vragen.
