Pada Oktober 1795 George Bass dan Matthew Flinders, disertai oleh William Martin berlayar dengan bot Tom Thumb dari Port Jackson ke Botany Bay dan menerokai Sungai Georges jauh ke hulu daripada yang telah dilakukan oleh penjajah sebelumnya. Laporan mereka ketika mereka kembali membawa kepada penempatan Banks' Town.[25] Pada Mac 1796 kumpulan yang sama memulakan pelayaran kedua dalam bot kecil yang sama, yang juga dikenali sebagai Tom Thumb.[26] Semasa lawatan ini, mereka mengembara sejauh pantai Tasik Illawarra, yang mereka panggil Tom Thumb Lagoon. Mereka mendapati dan meneroka Port Hacking. Pada 1798–99, Bass dan Flinders menyiapkan sekoci dan mengelilingi Tasmania, sekali gus membuktikan ia sebuah pulau.[27]

Panduan dan bantuan Orang Asli dalam penerokaan Eropah di tanah jajahan adalah biasa dan selalunya penting untuk kejayaan misi. Pada 1801–02 Matthew Flinders dengan The Investigator memimpin ekspedisi mengelilingi Australia yang pertama. Di atas kapal ialah peneroka Orang Asli Bungaree, dari daerah Sydney, yang menjadi orang pertama yang dilahirkan di benua Australia mengelilingi benua Australia.[27] Sebelum itu, Bennelong yang terkenal dan seorang rakan telah menjadi orang pertama yang dilahirkan di kawasan New South Wales untuk belayar ke Eropah, apabila, pada tahun 1792 mereka mengiringi Gabenor Phillip ke England dan telah dipersembahkan kepada Raja George III.[27]

Pada 1813, Gregory Blaxland, William Lawson dan William Wentworth berjaya menyeberangi halangan galur hutan dan tebing curam menggerunkan di Blue Mountains, barat Sydney, dengan mengikuti rabung berbanding mencari laluan melalui lembah-lembah. Di Gunung Blaxland mereka melihat "rumput yang cukup untuk menyokong ternakan tanah jajahan selama tiga puluh tahun", dan pengembangan penempatan British ke kawasan pedalaman boleh bermula.[28]

Pada tahun 1824 Gabenor Sir Thomas Brisbane, menugaskan Hamilton Hume dan bekas Kapten Tentera Laut Diraja William Hovell untuk memimpin ekspedisi mencari padang ragut baru di selatan jajahan itu, dan juga untuk mencari jawapan kepada misteri ke mana sungai barat New South Wales mengalir. Dalam tempoh 16 minggu pada 1824–25, Hume dan Hovell mengembara ke Port Phillip dan kembali. Mereka membuat banyak penemuan penting termasuk Sungai Murray (yang mereka menamakan Hume), kebanyakan anak sungainya, dan tanah pertanian dan ragut yang baik antara Gunning, New South Wales dan Corio Bay, Victoria.[29]

Charles Sturt mengetuai ekspedisi di sepanjang Sungai Macquarie pada tahun 1828 dan menemui Sungai Darling. Sebuah teori telah dibangunkan bahawa sungai-sungai pedalaman New South Wales menyalir ke dalam laut pedalaman. Mengetuai ekspedisi kedua pada tahun 1829, Sturt mengikuti Sungai Murrumbidgee ke dalam 'sebatang sungai yang luas dan besar', Sungai Murray, yang dinamakan sempena Sir George Murray, Setiausaha Negara bagi Tanah Jajahan. Kumpulannya kemudian mengikuti sungai ini ke persimpangan Sungai Darling, berhadapan dengan dua pertemuan yang mengancam nyawa dengan Orang Asli tempatan di pertengahan jalan. Sturt terus menyusuri sungai ke Tasik Alexandrina, di mana Murray bertemu dengan laut di Australia Selatan. Dengan penat lelah, kumpulan itu terpaksa mendayung kembali beratus-ratus hulu kilometer ke hulu untuk perjalanan balik.[30]

Jurukur Am Sir Thomas Mitchell menganjurkan beberapa siri ekspedisi dari 1830-an untuk 'mengisi ruang' yang ditinggalkan oleh ini ekspedisi sebelumnya. Beliau dengan cermat berusaha merekodkan nama-nama asal tempat Orang Asli sekitar jajahan itu, yang mana menjadi sebab majoriti nama-nama tempat hingga ke hari ini mengekalkan gelaran Orang Asli.[31]

Para saintis/peneroka Poland Count Paul Edmund Strzelecki menjalankan kerja pengukuran di Alps Australia pada tahun 1839 dan menjadi orang Eropah pertama mendaki puncak tertinggi di Australia, yang beliau namakan Gunung Kosciuszko sebagai penghormatan kepada patriot Poland Tadeusz Kosciuszko.[32]