Nama New Holland pertama kali digunakan untuk pantai barat dan utara Australia pada tahun 1644 oleh pelaut Belanda Abel Tasman, terkenal kerana penemuan Tasmania (dipanggil olehnya Van Diemen's Land). Kapten Inggeris William Dampier menggunakan nama dalam laporan dua pelayaran di sana: yang pertama tiba pada 5 Januari 1688 dan tinggal sehingga Mac 12;[1] pelayaran penerokaan keduanya ke rantau ini telah dibuat pada tahun 1699.[2] Melainkan memberi nama kepada tanah besar tersebut, baik Belanda serta Syarikat Hindia Timur Belanda tidak menuntut mana-mana wilayah di Australia sebagai miliknya. Walaupun banyak ekspedisi Belanda melawat kawasan pantai sepanjang 200 tahun selepas lawatan Belanda yang pertama pada 1606, Tidak ada sebarang usaha penubuhan penempatan yang tetap. Sebahagian besar peneroka tempoh ini menyimpulkan bahawa kekurangan air yang ketara dan tanah yang kurang subur menjadikan rantau itu tidak sesuai untuk penjajahan.

Pada 22 Ogos 1770, selepas belayar ke utara di sepanjang pantai timur Australia, James Cook menuntut keseluruhan pantai yang beliau baru sahaja diterokai sebagai wilayah British. Cook menamakan tanah itu New Wales, tetapi disemak semula kepada New South Wales.[3] Dengan penubuhan penempatan di Sydney pada 1788, British mengukuhkan tuntutannya ke atas bahagian timur Australia, kini secara rasmi dipanggil New South Wales. Dalam pelakuan kepada Gabenor Phillip sempadan telah ditakrifkan di longitud timur meridian ke-135 (135° timur),[4] (26 Januari 1788 - Peta) mengambil garisan dari peta Melchisédech Thévenot, Hollandia Nova‒‒Terre Australe, diterbitkan dalam Relations de Divers Voyages Curieux (Paris, 1663).[5]

Istilah New Holland telah lebih kerap digunakan untuk merujuk hanya kepada bahagian benua yang belum menjadi sebahagian kepada New South Wales; iaitu merujuk kepada bahagian barat benua. Pada tahun 1804, pengemudi British Matthew Flinders mencadangkan nama Terra Australis atau Australia bagi keseluruhan benua, dengan tidak membuang nama "New Holland" untuk bahagian barat benua itu. Beliau terus menggunakan "Australia" dalam surat-menyurat beliau, ketika cuba untuk mengumpul sokongan untuk istilah itu. Flinders menjelaskan dalam surat kepada Sir Joseph Banks:

Kesesuaian nama Australia atau Terra Australis, yang saya gunakan untuk seluruh dari apa yang biasanya dipanggil New Holland, hendaklah dikemukakan kepada perkenan Admiralti dan dipelajari dalam geografi. Ia kelihatan kepada saya satu perkara yang tidak konsisten bagi New South Wales kapten Cooks harus diserap dalam New Holland Belanda, dan oleh itu saya telah kembali kepada nama asal Terra Australis atau Tanah Besar Selatan, yang mana ia dibezakan walaupun oleh Belanda pada abad ke-17; dengan kelihatan bahawa tidak lama selepas pelayaran kedua Tasman yang nama New Holland itu mula-mula digunakan, dan kemudian sudahpun lama T’Zuydt Landt dibuang dari dalam peta, dan tidak tahu istilah apa lagi yag pernah wujud; New South Wales, oleh itu, patut kekal berbeza daripada New Holland; tetapi memandangkan adalah syarat bahawa seluruh benua perlu mempunyai satu nama umum, kerana ia kini dikenali (jika tidak ada kesalahan besar pada bahagian Belanda) bahawa ia sudah pasti semua adalah satu daratan, jadi saya putuskan, yang adil dan saksama bagi semua pihak tanpa sebarang perbalahan.[6][7]

Cadangan beliau pada mulanya ditolak, tetapi nama baru telah diluluskan oleh kerajaan British pada 1824. Sempadan barat New South Wales telah ditukar ke 129° timur pada 1825 (16 Julai 1825 - Peta). Pada 1826, untuk mengelakkan penempatan dan tuntutan wilayah oleh Perancis, kerana kepentingan laluan ke New South Wales, British menubuhkan penempatan Albany di barat daya New Holland. Gabenor Ralph Darling dari New South Wales meletakkan Edmund Lockyer untuk mengetuai ekspedisi dan memberinya arahan bahawa jika beliau bertembung dengan Perancis di mana tentera beliau mendarat, tunjukkan kepada mereka bahawa "seluruh New Holland adalah tertakluk kepada Kerajaan Baginda Raja Britain."[8] Pada tahun 1828 penempatan lanjut dibuat, kali ini di Sungai Swan, dan nama Koloni Sungai Swan dijadikan istilah yang digunakan untuk merujuk kepada bahagian barat seluruh benua. Nama New Holland masih dipanggil sebagai nama bagi seluruh benua apabila pada 9 Mei 1829 Charles Fremantle mengambil alih secara rasmi atas nama Raja George IV "semua bahagian New Holland yang tidak termasuk dalam wilayah New South Wales."[9]:p11 Pada tahun 1832, wilayah ini telah ditukar secara rasmi kepada Australia Barat.

Walau selewat tahun 1837, dalam surat-menyurat rasmi antara kerajaan British di London dan New South Wales, istilah "New Holland" masih digunakan untuk merujuk kepada benua secara keseluruhan.[10][11]

Di Belanda, benua itu terus dipanggil Nieuw Holland sehingga kira-kira akhir abad ke-19. Nama Belanda hari ini ialah Australië.