Obwohl Australien der westlichen Welt nicht bekannt war, spielte es doch in der  spätmittelalterlichen Logik und Mythologie eine bedeutende Rolle, denn man nahm zu dieser Zeit an, dass ein großes so genanntes Südland, das von den Geographen auch als Terra Australis Incognita bezeichnet wurde, zur Ausbalancierung der nördlichen Landmassen in Europa und Asien notwendig sei. Die Terra Australis erschien auf den frühen europäischen Weltkarten häufig
als große, kugelförmige Masse, die zufällig ungefähr die der Realität entsprechende geographische Lage einnahm, obwohl von den Europäern erst sehrviel später echte Entdeckungen dokumentiert wurden.


1. Portugiesische und spanische Entdeckungsreisen

Infolge der systematischen Erforschung der afrikanischen Westküste in südlicher Richtung, die von den Portugiesen im 15. Jahrhundert auf der Suche nach einer Handelsroute nach Indien vorgenommen wurde, entfachte sich das Interesse der Europäer an der Entdeckung der legendären Terra Australis erneut. Portugal, das schon bald den Handel mit Indien und Ostafrika
dominierte, verlor jedoch das Interesse daran, weiter in östlicher und südlicher Richtung vorzustoßen. Aber auch aus anderen Gründen blieb Australien in der darauf folgenden Zeit weiterhin unentdeckt. Zunächst einmal befand es sich abseits des ozeanischen Handelskorridors im Indischen Ozean und im Südpazifik. Zusätzlich dazu driften die Windsysteme der südlichen Hemisphäre hier in nördlicher Richtung zum westlich von Australien liegenden Bereich des Äquators ab, während die starken Gegenwinde östlich des australischen Festlandes das Segeln entgegen der ausgeprägtenWindsysteme erschwerten.

Im 16. und frühen 17. Jahrhundert entsandte Spanien, das zu dieser Zeit bereits seine Vormachtstellung als Kolonialreich in Süd- und Zentralamerika gesichert hatte, einige Expeditionsschiffe von Peru in den Südpazifik. Die offiziellen Vertreter der spanisch dominierten Neuen Welt wurden durch die Entdeckung der Salomon-Inseln  nordöstlich von Australien durch Álvaro de Mendaña 1567 dazu ermutigt, 1595 und 1605 Expeditionen zu entsenden, von denen sie sich erhofften, für das Spanische Reich Gold und für die römisch-katholische Kirche die Terra
Australis zu entdecken. Nach dem Fehlschlag dieser Entdeckungsreisen, die weder die erhofften Edelmetalle mitbrachten noch die Entdeckung bedeutender Landmassen zur Folge hatten, verlor Spanien sein Interesse an derartigen Unternehmungen und führte keine weiteren Expeditionen mehr durch.

 
2. Niederländische Interessen
 
Die wirtschaftliche Verflechtung Portugals mit Indien und die Entmutigung der Spanier von weiteren Forschungsunternehmungen ermöglichten den Niederlanden als aufstrebender Macht im 17. Jahrhundert die Errichtung einer Reihe von Handelszentren, die sich vom Kap der Guten Hoffnung bis nach Niederländisch-Indien (Indonesien) zogen. Die Niederländer, die ihre Niederlassungen vorwiegend in den indonesischen Hafenstädten Bantam und Batavia (Jakarta) hatten, ließen den europäischen Traum von der Entdeckung Australiens schon bald zur Wirklichkeit werden. Mit Hilfe besserer Segelschiffe waren sie in der Lage, die widrigen Gegebenheiten im Südpazifik erfolgreich zu überwinden. Anfang 1606 drang Willem Janszon mit seinem Segelschiff in die Torresstraße vor, die zwischen dem australischen Festland und Neuguinea verläuft, und sichtete einen Teil der australischen Nordküste an der Westseite der Kap-York-Halbinsel, den er Kap Keer-Wear taufte. Die von ihm befahrene Wasserstraße wurde später nach Luis Vaez de Torres benannt, dem letzten der spanischen Forschungsreisenden, der nur wenige Wochen später in das gleiche Gebiet segelte und schlussfolgerte, dass Neuguinea eine Insel sei, Australien jedoch mit fast hundertprozentiger Sicherheit nicht sichtete.

Niederländische Generalgouverneure in Batavia fühlten sich nach den Reisen von Janszon dazu ermutigt, weitere Expeditionen in den südlichen Ozeanen zu veranlassen. Im Oktober 1616 wurde die Eendracht unter dem Kommando von Dirk Hartóg das erste Schiff, von dem aus Europäer an der Shark Bay in Western Australia australischen Boden betraten. Zwischen 1626 und 1627 erforschte Peter Nuyts ungefähr 1 600 Kilometer der südaustralischen Küste, und andere
Niederländer vervollständigten das noch bruchstückhafte Bild des neuen Kontinents durch Informationen über die Nord- und Westküste. Die bedeutendste Entdeckungsarbeit leistete jedoch Abel Janszoon Tasman , der 1642 nach der Erforschung der Meere in die Gewässer Südaustraliens segelte und die Westküste der heute als Tasmanien bekannten Insel sichtete. Tasman taufte diese Insel nach dem Gouverneur von Niederländisch-Indien, der diese Expedition initiiert hatte, auf den Namen Van Diemen's Land. Danach drang er weiter in östlicher und nördlicher Richtung vor und entdeckte Neuseeland. Tasman unternahm 1644 eine zweite Expedition zur Nordküste. Trotz der rasch voranschreitenden Erforschung des Kontinents, der von seinen ersten Entdeckern Neuholland genannt wurde, ließen die Niederlande ihren Neuentdeckungen keine formelle Inanspruchnahme im Namen des eigenen Landes folgen. Ihrem Ermessen nach boten diese Gebiete nur wenig, was für den europäischen Handel von Interesse
hätte sein können. So stand der später folgenden Ankunft der Engländer nichts im Weg.

3. Britische Expeditionen und Besitzergreifung
 
Zu Beginn schien dem Interesse der britischen Regierung an Australien das gleiche Schicksal wie bei den Spaniern und den Niederländern bestimmt zu sein. 1688 ging der englische Seeräuber William Dampier im Nordwesten an Land. Nach seiner Rückkehr nach England veröffentlichte er das Buch Voyages und überredete die Verantwortlichen der Marine, eine erneute Fahrt finanziell zu unterstützen, um nach den angeblichen Reichtümern des Landes zu forschen. Die zweite Expedition von Dampier, bei der er in den Jahren 1699 bis 1700 rund 1 600
Kilometer an der Westküste entlangsegelte, führte zu der detailliertesten Dokumentation dieses Kontinents in der damaligen Zeit, schilderte jedoch das Land und seine Bevölkerung in dermaßen trostloser Art und Weise, dass die Engländer (ab 1707 Briten) ihr Interesse an einer weiteren Erforschung Australiens für die folgenden 70 Jahre verloren.

1768 verließ Kapitän James Cook mit der Unterstützung der britischen Admiralität auf der ersten seiner insgesamt drei Entdeckungsreisen England. Die drei Jahre dauernde Expedition führte ihn u. a. auch nach Australien. 1770 entdeckte Cook die Botany Bay an der Ostküste und landete im Norden bei Possession Island, wo er am 23. August die Gegend im Namen der britischen Krone in Besitz nahm und auf den Namen New South Wales taufte. Er und seine Mannschaft, zu der auch der Botaniker Sir Joseph Banks  gehörte, befürworteten später die Besiedlung Australiens. Cooks zweite und dritte Entdeckungsreise in den siebziger Jahren ergänzten die bereits vorhandene Information über Australien und festigten die britische Anspruchshaltung auf den Kontinent.

Das Interesse Frankreichs war weniger ausgeprägt als das von Großbritannien. Marion Dufresne konzentrierte sich bei seiner Fahrt 1772 auf die Anfertigung von Landkarten und die Beschreibung der unwirtlicheren Westküste Tasmaniens, und später erkundeten französische Seefahrer die Südküste von Australien. Zu diesem Zeitpunkt hatten die Briten jedoch bereits die erste australische Siedlung eingerichtet und von der östlichen Hälfte des Kontinents Besitz
ergriffen. Trotz der anhaltenden Bemühungen der Briten wurden die australischen Küsten
erst im 19. Jahrhundert vollständig erkundet. Matthew Flinders , ein Marineoffizier, umrundete in
der Zeit von 1801 bis 1803 erstmals den gesamten Kontinent. Er erfasste einen Großteil der Küstenlinie kartographisch und konnte dadurch belegen, dass es sich bei Australien um eine einzige große Landmasse handelte. Bereits 1798 hatte Flinders zusammen mit dem Marinearzt George Bass erstmals Tasmanien umsegelt und so dessen Inselform bewiesen. Flinders Bemühungen ist es außerdem zu verdanken, dass der Kontinent nicht den Namen Neuholland beibehielt, sondern auf seinen Vorschlag hin in Anlehnung an Terra Australis ab 1817 offiziell als
Australien bezeichnet wurde. Obwohl die Küsten bereits weitestgehend kartographiert worden waren, besaß man in Europa erst in den siebziger Jahren des 19. Jahrhunderts detailliertere Informationen über diewichtigsten geographischen Strukturen im Inland.