After departing from Amboyna on 21 January 1623 in the Pera accompanied by Willem Joosten Van Colster in the Arnhem the two ships followed the south coast of New Guinea, then crossed the unknown Torres Strait to the Cape York Peninsula and the Gulf of Carpentaria.
Progress along an uncharted, almost unknown coast was slow, due to a combination of shoals and reefs in the water and the need to make frequent landings to replenish supplies of fresh water and firewood.
Along the way they sighted the mountain now known as Carstensz Pyramid, Carstensz' claim to have sighted the glaciers on the peak attracted ridicule in Europe from sceptics who believed it was not possible to find snow near the equator.
On 11 February a landing on the coast of New Guinea saw the master of the Arnhem and ten of his crew killed in conflict with the local people.
They were still in New Guinea waters at the end of March, when Carstensz decided to go south and made landfall on Cape York 12 April somewhere near Port Musgrave. As the ships continued to sail south, landings found little fresh water and nothing of commercial interest.
On 14 April 1623, the two ship passed Cape Keerweer, the Duyfken's most southerly point, and landed, seeking fresh water and firewood, Carstenszoon encountered a party of Wik people. Carstensz' journal described them as "poor and miserable looking" without "knowledge of precious metals or spices".
On 24 April, near the southern end of the Gulf of Carpentaria, a tablet recording the voyage was placed ashore near the Staaten River, and two days later they turned north.