For many centuries Europeans believed there must be a vast land in the southern hemisphere, variously called ‘Terra Australis Incognita’ or ‘Unknown South Land’.
After Dutch navigators charted the northern, western and southern coasts of Australia during the 17th Century this newly found continent became known as ‘New Holland’.
It was the English explorer Matthew Flinders who made the suggestion of the name we use today. He was the first to circumnavigate the continent in 1803, and used the name ‘Australia’ to describe the continent on a hand drawn map in 1804.
When the map and book describing his journey was finally published in 1814 the name 'Terra Australis' was used instead, although Flinders stated that his preference was still 'Australia'. You can view his General chart of Terra Australis or Australia map online.
The name Australia had appeared in print before, but only broadly applied to the legendary southern land mass. The earliest printing of this name is in an astronomical treatise published in 1545. With south at the top of the map a small wind head map names the imagined southern land mass ‘Australia’.
The State Library of South Australia has an excellent overview of Flinders' naming of Australia on their website Encounter 1802-2002.
Some relevant material held by the National Library includes:
A voyage to Terra Australis , the published account by Flinders of his journey around Australia.
General chart of Terra Australis or Australia [cartographic material] : showing the parts explored between 1798 and 1803 by M. Flinders Commr. of H.M.S. Investigator. This is also available to view online.