Wyprawa wyruszyła z Ambon w styczniu 1623 na dwóch statkach o nazwach: „Pera”, dowodzonym przez Carstenszoona, i „Arnhem”, którego kapitanem był Dirk Meliszoon. 11 lutego statki dotarły do Nowej Gwinei, gdzie doszło do konfliktu z tubylcami wskutek którego zginął kapitan „Arnhem” i 10 innych osób. Po śmierci Meliszoona, „Arnhem” przeszedł pod komendę Willema van Colstera.
Wyprawa udała się dalej na południe i pod koniec marca 1623 żeglarze znaleźli się w rejonie Cieśniny Torresa. Zamiast przepłynąć przez cieśninę, wpłynęli na wody Zatoki Karpentaria, myśląc, podobnie jak Jansz 17 lat wcześniej, że widoczny na wschodzie Półwysep Jork należy do Nowej Gwinei.
12 kwietnia gdzieś w pobliżu dostrzeżono ląd – Australię. 24 kwietnia ustawiono tablicę upamiętniającą wyprawę na południowym krańcu Zatoki Karpentaria. Następnie pożeglowano na północ i 14 maja podróżnicy znaleźli się w pobliżu ujścia . Wyprawa dotarła do ujścia rzeki, którą nazwano Staaten Rivier (Staaten River). Wkrótce potem van Coolsteerdt odłączył się od wyprawy, obierając kurs powrotny do Ambon przez wyspy i Kai. Płynąc zachód, sporządzał mapy obszarów po drugiej stronie zatoki – regionu znanego obecnie jako Ziemia Arnhema.