Lange vor der Entdeckung Australiens hatten Gelehrte im alten Europa die Existenz eines Südkontinentes behauptet. Häufig wird das rätselhafte „Südland“ (lat. terra australis) erwähnt. Marco Polo segelt 1292 von China zurück nach Venedig und erwähnt ein an Gold und Muscheln reiches Land südlich von Java.
Im 16. und 17. Jahrhundert erreichen vermutlich portugiesische, französische und spanische Seefahrer die Küsten Australiens und gehen an Land. Als gesichert gilt allerdings erst die Entdeckung der Cape York Peninsula durch den Niederländer Willem Jansz im Jahre 1606. 1616 betrat Dirk Hartog die australische Westküste. Im Juli 1629 strandete das Handelsschiff Batavia der Niederländischen Ostindienkompanie an der Westküste, aber dessen Kommandeur François Pelsaert maß seiner Entdeckung keine entscheidende Bedeutung zu. Erst im Jahre 1642 entschloss sich die Niederländische Ostindien-Kompanie, den Kontinent durch eine geplante Expedition zu erforschen. Abel Tasman entdeckte dabei das heutige Tasmanien. Eine weitere Expedition, die im Jahre 1696 unter Willem de Vlamingh begann, kartografierte Teile der Westküste Australiens. Da die Landschaft aber trocken und unfruchtbar wirkt, zeigten die Holländer kein Interesse, Australien zu kolonisieren. Tasman prägte 1644 die Bezeichnung „Neuholland“, die bis 1824 in Gebrauch war, erst dann führten die Briten den heute gültigen Namen ein.