В 1829 г. на юго-западе Австралии были основаны два города: в устье р. Суон (Лебединая) — Перт, у бухты Кинг-Джордж — Олбани. Оттуда, чтобы расширить территорию колонии, совершались в глубь страны походы, пока не очень далекие. В первую очередь был открыт к востоку от Перта хребет Дарлинг, а к северу от Олбани — хребет Стерлинг, названный в честь основателя колонии Джеймса Стерлинга. Летом 1830/31 г. офицер Томас Баннистер прошел от Перта до Олбани и обнаружил, что эта страна (юго-западный угол Австралии) годна для колонизации.

В начале 1839 г. офицер Джордж Грей начал исследование западного побережья Австралии: он высадился на островок в заливе Шарк и у 25° ю.ш. открыл устье р. Гаскойн. Вскоре во время шторма партия лишилась большей части провизии. Грей направился к югу морем на трех лодках, но за 28-й параллелью потерпел крушение в бухточке, куда впадала сравнительно крупная река (Мерчисон). Остальную часть пути до Перта — около 500 км — пришлось идти пешком вдоль берега, который произвел на Грея более благоприятное впечатление, чем на его предшественников-моряков, но оно не подтвердилось дальнейшими исследованиями.

В 1836 г. на берегу залива Сент-Винсент возник город Аделаида — центр Южной Австралии. Он стал отправной базой для экспедиций, цель которых состояла главным образом в поисках пастбищных угодий. В мае 1839 г. овцевод Эдуард Джон Эйр, обследуя приморскую полосу у залива Спенсер, открыл почти меридиональный хребет Флиндерс с высотами до 1189 м, к западу от него — соленое озеро Торренс (до 5,7 тыс. км²). В июле этого же года, исследуя у залива Спенсер п-ов Эйр, овцевод обнаружил в его северной части невысокий хребет Годер.

В конце июля 1840 г., пройдя на север от залива Спенсер, Эйр выяснил, что озеро Торренс превратилось в солончак. Дальше на севере он открыл другое соленое озеро, которое счел продолжением Торренса. С одной из вершин хребта Флиндерс Эйр увидел на востоке большой солончак, также принятый им за часть громадного «подковообразного» Торренса. В 1843 г. Э. Фром доказал ошибочность этого предположения: пройдя вдоль восточного склона хребта, он убедился, что соленое озеро Фром (2—3 тыс. км²) — изолированный бассейн. Позднее (в 1858—1860 гг.) было установлено, что это отдельный водоем, названный озером Эйр (до 15 тыс. км²). Вернувшись к морю, Эйр с небольшим отрядом прошел берегом на запад, получая от другого отряда, плывшего на судне, воду и съестные припасы: на суше в этой пустынной полосе нельзя было достать ни пищи, ни воды. Эйр остановился у 132°30' в.д. и отослал судно к заливу Спенсер за провизией и свежей водой. Судно возвратилось к нему в конце января 1841 г., но Эйр направился берегом дальше на запад лишь через месяц, сократив число спутников до пяти человек, из них к 27 июля, когда он прибыл в бухту Кииг-Джордж (у 118° в.д.), умерло трое. Во время этого четырехмесячного перехода Эйр и молодой австралиец Уайли прошли свыше 2000 км, большей частью через совершенно безводную пустыню, вдоль равнины, за которой закрепилось название Nullarbor (латинское — «Ни одного дерева»), в английском произношении Налларбор.

В конце 1848 г. топограф Огастес Грегори, пройдя от Перта прямо на север около 500 км. открыл и обследовал бассейн р. Мерчисон. Он пытался продвинуться от ее среднего течения на северо-запад, к заливу Шарк, но отступил перед пустыней. В 1852 г. он повторил попытку и на этот раз достиг залива Шарк.