Tämä ei kuitenkaan seisauttanut siirtolaisuutta. Yhä laajemmalle ja laajemmalle uudisasukkaat retkeilivät etsiäkseen uusia laitumia kasvaville laumoilleen ja karjoilleen ja vähitellen syntyi aivan uusi uudisasukasluokka, joka ei odottanut hallituksen alotetta, vaan oli tottunut toimimaan omin neuvoin ja itseään varten.
Tämänlaatuisia miehiä oli Edward John Eyre. Hän oli ensimmäinen, joka kuljetti karjaa Port Philipistä, nykyisen Melbournen seuduilta, nykyisen Etelä-Austraalian pääkaupunkiin Adelaideen, jonka pohjoispuolella hänellä oli pieni tila, V. 1838 hän teki tutkimusmatkan »Onnellisen Austraalian» takamaahan, seuraten Mitchellin löytämää Wimmera jokea järveen, johon se päättyi, ja tämä retki herätti niin suurta huomiota, että tutkimusretkeilijää tarvittaessa huomio kääntyi etupäässä häneen. Hän oli lisäksi omin päin tutkinut Torrens-järven seutuja ja Flinders-vuoristoa, joka Spencer-lahden pohjasta kulkee sisämaahan. Kun v. 1840 Adelaiden uudisasukkaat kaipasivat miestä, joka tutkisi maantien suunhan Länsi-Austraalian siirtokuntiin, oli Eyren nimi ensimmäisenä kaikkien huulilla. Eyre suostui lähtemään.
Etelä-Austraalia oli silloin jo eronnut Uudesta Etelä-Walesista itsenäiseksi siirtokunnaksi, jonka hallitus pienellä summalla kannatti Eyren retkeä. Lähes toisen puolen keräsivät uudisasukkaat ja täyden toisen puolen Eyre suoritti omista varoistaan. Kesäkuussa 1840 hän, viisi valkoista ja kaksi mustaa seuralaisinaan, lähti Adelaidesta Spencer-lahden pohjukkaan, jonne matkavarustukset oli vietävä purjealuksella.
Torrens-järvellä.
Odotellessaan lahden päässä purjealusta Eyre mustan pojan keralla uudelleen käväisi Torrens-järven seuduilla, jotka sillä kerralla näyttivät vielä tavallistakin kehnommilta. Hän kulki useitten kuivuneiden suolajärvien poikki, joiden uoma nyt oli valkoisena suolakiteistä, ja missä vettä oli, oli se suolaisempaa kuin valtamerenkin. Veden löytäminen tuotti loppumatonta vaivaa, jota vielä suunnattomasti lisäsivät kangastukset. Kangastuksia näillä seuduin todella näkyi niin tiheään, että sekä Eyre että hänen musta palvelijansa jos kuinka monta kertaa luulivat löytäneensä kauniin järven, joka kuitenkin heidän paikalle kiirehtiessään katosi olemattomiin.
Leiriin palatessaan ei heillä ollut muuta kerrottavaa, kuin että vettä ja laidunta oli sangen vähän ja että alkuasukkaat olivat kovin arkoja ja huonon näköisiä.
Eyre jätti nyt suurimman osan varastoitaan säilöön Spencer-lahden pohjukkaan ja lähti suuremmalla joukolla pohjoista kohti samaa reittiä, jonka hän vast'ikään oli käynyt. Vettä ja laidunta oli kuitenkin niin niukalta, että taipaleen teko kävi kovin työlääksi. Alkuasukkaita oli vähän, mutta nämäkin vähät osoittivat vihamielisyyttä, vaikk'eivät uskaltaneetkaan ryhtyä väkivallan töihin. Kaksi kuukautta Eyre turhaan yritti tunkeutua Torrens-järveä ympäröiväin autioiden seutujen kautta, löytäen muun muassa Eyre-järven eteläpään, jota hän luuli Torrens-järven jatkoksi. Tyhjin toimin retkikunnan täytyi palata varastolleen.
Kun yritys löytää lännempää reitti niinikään oli turha, päätti Eyre kulkea Länsi-Austraaliaan merenrantaa pitkin, jota varten hän vähensi joukkoaan, lähettäen kaksi miestä takaisin Adelaideen ja tuottaen sieltä uusia matkavarustuksia.
"Suuren mutkan" ranta.
Näitä odotellessaan hän yhden valkoisen ja yhden mustan kanssa vakoili eteisiä seutuja, tutkien maan aina suuren mutkan pohjukkaan saakka. Maa oli kuivaa, karua ja hietaista eikä ruohoa sen enempää kuin vettäkään ollut kuin hyvin niukasti. Eräältä alkuasukasheimolta hän kuuli, että sisämaahan täytyi kulkea viisi päivämatkaa, ennenkuin vettä löytyi, ja merenrantaa seuraillen kuusi päivämatkaa. Eyre näine tietoineen palasi leiriinsä, joka oli muutettu Spencer-lahdesta kappaleen matkaa lännemmäksi.