早在古希臘時代，亞里斯多德便提出了原始的「平衡大陸」理論，他認為在地球相對應的地區存在一片「未知的南方大陸」（Terra Australis Incognita）。後來這個理論被托勒密延伸，他相信印度洋就位在未知的南方大陸附近，這樣才能跟北半球的大陸達成平衡。這個假想的大陸常見於中世紀地理學，人們依據平衡大陸理論，將這片從未探索過、也從未有文獻記載的大陸畫在地圖上。

　　1644年，荷蘭航海家亞伯‧塔斯曼（Abel Tasman）途經澳洲西部和北部海岸時，把澳洲稱呼為「新荷蘭」（New Holland）。塔斯曼最著名的是發現塔斯馬尼亞島（Tasmania），當時他將這座島命名為范迪門斯地（Van Diemen's Land）。自此之後，新荷蘭這個名字開始廣泛應用在歐洲地圖上，用來指稱所謂的「南方大陸」（當時認為澳洲屬於未知的南方大陸的一部分，即使在探索完澳洲的海岸線後依然如此稱呼）。

　　但除了為這片土地命名以外，荷蘭和荷蘭東印度公司從未在澳洲大陸宣稱過任何領土。雖然在1606年荷蘭人第一次造訪澳洲後的200年間，有許多荷蘭探險隊曾到達澳洲海岸，但從沒有人嘗試建立一個永久定居點。這個時期的大多數探險家得出的結論是，這片土地明顯缺乏淡水與肥沃的土壤，因此並不適合殖民。

　　1770年8月22日，英國「奮進號」（Endeavour）船長詹姆斯‧庫克上尉（James Cook）沿著澳洲東海岸向北航行後，宣稱剛探索完的「新荷蘭東海岸」全都屬於英國領土。庫克船長剛開始把澳洲東海岸命名為新威爾斯（New Wales），後來才改為新南威爾斯（New South Wales）。隨著1788年在雪梨建立殖民地，英國人逐漸鞏固了澳洲東部的主權，將邊界劃定在東經135度，並開始思考為這片土地取一個新的名字。

　　當時的「新荷蘭」只用於指代還沒被新南威爾斯佔領的其餘地區；也就是說，新荷蘭通常是指澳洲西半部。1804年，英國航海家馬修‧弗林德斯（Matthew Flinders）提出把整個大陸改為澳洲大陸或澳洲，而西半部繼續沿用「新荷蘭」。他開始在書信中改用「澳洲」一詞，同時爭取人們支持這個新名稱，弗林德斯在寫給約瑟夫‧班克斯爵士（Joseph Banks）的信中解釋說：

　　「我已經把澳洲或澳洲大陸這個名字用來指代所謂的『新荷蘭』，至於這個名稱是否恰當，還必須徵得海軍與地理學家的同意。在我看來，庫克船長把新南威爾斯納入荷蘭人命名的新荷蘭是一件很矛盾的事情，因此我主張恢復它原本的名字：澳洲大陸或南方大陸，荷蘭從17世紀就用這個名稱來區分；似乎是直到塔斯曼第二次航行後的某個時間點，人們才開始改用新荷蘭；因此，新南威爾斯應該與新荷蘭有所區別；既然現在大家都知道這片土地確實屬於同一塊大陸（如果沒有荷蘭這個錯誤的部分），而整個大陸必須使用一個通用的名稱，所以我認為集合各方因素，應該採用澳洲這個比較不容易引起異議的名稱。」

　　弗林德斯的建議一開始被拒絕，但不久後於1824年被英國政府批准。1825年，新南威爾斯的西部邊界改為東經129度。1826年，為了先發制人搶在法國人之前佔領通往新南威爾斯的重要航線，英國人在新荷蘭的西南部建立起奧班尼定居點。新南威爾斯總督拉爾夫‧達林（Ralph Darling）任命艾德蒙‧洛克耶（Edmund Lockyer）率領遠征隊，命令他在任何地方遇見法國人都要讓軍隊登陸上岸，並向法國人宣示「新荷蘭的全部地區都從屬於英國政府」。

　　1829年5月9日，英國皇家海軍軍官查理斯‧費里曼特爾（Charles Fremantle）以國王喬治四世的名義正式佔領「不包括在新南威爾斯領土內的所有新荷蘭地區」，可見當時新荷蘭還是用於指代整個澳洲大陸。1832年，新荷蘭被正式更名為西澳洲。但直到1837年，英國政府與新南威爾斯的官方書信中，仍然可以見到雙方使用「新荷蘭」一詞稱呼整個澳洲大陸。

　　儘管英國殖民政權在19世紀時試圖逐步除去新荷蘭這個名稱，但它還是繼續存在了數十年，依然在當時的地圖、文學作品和一般對話被使用。