Tasman does little more than speak the prologue. The Dutch East India Company, his master, was more interested in profits than in mere knowledge. The voyage of 1642 was sent out by Anthony van Diemen, Governor-General of the Dutch East Indies, whose attention was drawn south by Franz Jacobs-zoon Visscher, a man of genuine scientific curiosity. Visscher speculated, as had European geographers over a lengthy period, upon the “demonstrable” existence of a great continent in the unknown south. Van Diemen was concerned to command its trade, if it were there; he was also interested in Australia, at that time known only in part, and in the Solomon Islands, discovered by Mendana in 1568 and not since visited. Tasman, accompanied by Visscher, was given two small ships, neither in very good condition, the Heemskerck and the Zeehaen, to go first to Mauritius and then east until, if it should so chance, he fetched up on the coast of the southern continent. Civilised men, if found, were to be treated with an eye to trade and the acquisition of gold or other precious metals.

In due course, sailing east, Tasman came to the island he called Van Diemen's Landt (Tasmania). Sailing further east over the sea named after him, Tasman saw, on 13 December 1642, the coast and mountains of a new land. He had, in fact, sighted the west coast of the South Island between Hokitika and Okarito. He turned north, followed the coast past Cape Foulwind into the Karamea Bight, around Cape Farewell, and into a peaceful bay. Here smoke was first seen on the shore; on 17 December, the two ships came to anchor. This bay is now called Golden Bay, but Tasman soon had reason to label it Murderers' Bay. His ships were inspected by canoes manned by men neither civilised nor friendly, savages who would not be interested in trade goods. It seems likely that the local Maoris gathered their forces to meet this menace – eventually no fewer than 22 canoes were seen. On 19 December, as a cockboat was going between the ships, it was set upon and four sailors were killed. The canoes were kept off the ships by gunshot, and one Maori was seen to have been hit. Tasman, unusually forbearing, left without setting foot on the shore.

His course took him into Cook Strait, but the winds prevented an examination of the coast which, it was realised, might reveal a passage east. Tasman named the new land Staten Landt, in honour of the States-General, and also because, were this the coast of the southern continent (as Tasman thought it well might be) it could be connected with that Staten Landt discovered in 1616 to the south of South America.

The ships then sailed up the western coast of the North Island, rounding Cape Egmont, and reaching Cape Maria van Diemen on 4 January 1643. Here Tasman resolved to land on the island he named Three Kings, for it was the eve of the season of Epiphany, to find water and vegetables. The boats were sent heavily armed, for warlike savages were seen on shore, but the surf, wind, and rocks prevented a landing. Tasman was back in Batavia in June 1643, having discovered Tonga and Fiji on the way.

The voyage had been a notable feat of discovery and seamanship, but it promised no commercial reward, and Dutch attention did not turn that way again. The name Staten Landt did not stick; in some way the name Nieuw Zeeland became attached to the coastline that Tasman had drawn, and that line, still possibly the edge of the southern continent, found its way into the atlases, and waited until Cook should complete it and correct it.