"Discovery" conventionally means "discovery by someone -- usually Europeans -- other than the original inhabitants." Text books credit Captain Cook with discovering Australia and New Zealand, but at the time "Captain Dalrymple, head of the Map Department at the British Admiralty. . . wrote a furious protest" (388): Cook could hardly have discovered Australia since he had in hand Admirality maps already depicting that continent! It turns out that the Chinese regularly journeyed to the Australia as early as the ninth century to mine copper, and fifteenth-century Chinese voyages of exploration led directly to the maps Cook used. As Gavin Menzies explains, "Cook's orders from the Admiralty were to explore down to 40 o S -- the latitude of South Australia shown on both charts -- where they 'had good reason' to suppose the Southern Continent existed. They certainly did -- they already had two charts showing such a continent at 40 o S (192).
Menzies's book on fifteenth-century Chinese exploration points to the following facts and deductions:
About Cook Menzies concludes:
Cook was a great man, and the greatest navigator of all time, but he discovered neither New Zealand nor Australia. More than two centuries before he embarked on his voyages, a cluster of maps from the Dieppe School showed Australia with remarkable clarity. The Jean Rotz map was in possession of the British Admiralty when Cook set sail, and Joseph Banks, who sailed with Cook, had acquired another of the finest, the Harleian (Dauphin), showing Australia with the same precision as the Rotz map . . . The Endeavour Reef, on which Cook later ran aground, is clearly shown on these earlier maps, together with what later became known as Cooktown Harbour. When Cook had extricated himself for the reef, he sailed directly for Cooktown, the only harbour in a thousand miles of costline. "This harbour will do excellently for our purposes, although it is not as large as I have been told." Desliens's map does indeed show it larger, for sea levels were lower when Admiral Zhou Man originally charted the coast in 1422-23. 
Menzies, Gavin. 1421: The Year the Chinese Discovered America. New York: William Morrow, 2003.
Last modified 27 June 2003