W krainie kangurów
W latach 30. XIX w. na mapie Australii wciąż widniało wiele białych plam. Dobrze spenetrowane i poznane były właściwie jedynie wybrzeża. Niewiele wiedziano także o geologii tego kontynentu. Europejczycy przybyli tu późno, a Wielka Brytania, która założyła w Australii swoje kolonie, przez wiele dziesięcioleci traktowała ją jako miejsce zsyłki więźniów. Dlatego wpływając do Sydney, największego miasta Australii, Strzelecki spodziewał się, że znajdzie się w stolicy rozpusty i przestępczości. Przeżył jednak miłe zaskoczenie, co podsumował słowami: „Zastałem jednak tej nocy na ulicach Sydney obyczajność i spokój, jakiego nie oglądałem nigdy w żadnym porcie Zjednoczonego Królestwa". Na dodatek władze brytyjskiej kolonii przyjmowały z otwartymi ramionami śmiałków przybywających z wielkiego świata, aby eksplorować nieznane ziemie. Strzeleckiego namawiano do podjęcia wypraw w kierunku północnym, ale on wolał skierować się na południe, uznając za najpilniejsze zbadanie nieznanego wówczas odcinka Wielkich Gór Wododziałowych. Podczas swojego czteroletniego pobytu w Australii i na Tasmanii poprowadził trzy wielkie wyprawy w głąb kontynentu, a każda z nich obfitowała w nowe i cenne odkrycia.
W swą pierwszą podróż w głąb australijskiego lądu Strzelecki wyruszył w lipcu 1839 r. Jej trasa wiodła w mało wówczas znane Góry Błękitne i dolinę górnego biegu rzeki Grose. Teren był odludny i trudny do przebycia. W swoim pamiętniku pod datą 8 września badacz zanotował: „Miałem do wyboru tylko jedną drogę: iść naprzód. Zdwoiłem przeto tempo marszu, wchodziłem do góry i schodziłem na dół, wspinałem się i zjeżdżałem, czołgałem się, aż znalazłem się w środku lasu z wysokimi i gęstymi paprociami uginającymi się pod ciężarem padającego wciąż deszczu. Mój dalszy marsz przypominał raczej pływanie niż chód". W końcu Strzelecki znalazł nieoznaczone na mapie ludzkie osiedle i kontynuował swoją podróż. Szczęście uśmiechnęło się do niego w okolicach Bathurst, gdzie natrafił na ślady złota. Przypadkowe odkrycia tego kruszcu zdarzały się tu już wcześniej, ale dopiero Strzelecki wyciągnął z tego naukowe wnioski. Po powrocie w listopadzie do Sydney spotkał się z gubernatorem Nowej Południowej Walii George'em Gippsem i pokazał mu próbki złota. Ten poprosił jednak Strzeleckiego o nierozgłaszanie informacji o odkryciu cennego kruszcu, obawiając się niepokojów w kolonii, której większość mieszkańców wciąż stanowili skazańcy. Strzelecki spełnił jego prośbę i w ten sposób gorączka złota, która odegrała tak istotną rolę w rozwoju i zasiedleniu Australii, opóźniła się o kilkanaście lat.
21 grudnia 1839 r. Strzelecki wyruszył w głąb nieznanego lądu po raz drugi. W lutym dołączyli do niego farmer James Macarthur i praktykujący u niego młody Anglik James Riley. Wspólnie ruszyli wzdłuż Gór Wododziałowych, badając okolice prawobrzeżnych dopływów rzeki Murrumbidgee i górny bieg rzeki Murray. Idąc na wschód, Strzelecki odkrył i zbadał najwyższe pasmo Gór Wododziałowych – Góry Śnieżne. 15 lutego wspiął się na mierzący 2228 m szczyt, który okazał się najwyższą górą Australii. Polski badacz nazwał go Górą Kościuszki. W dzienniku z wyprawy tak opisał ten moment: „Szczególny wygląd tego wierzchołka uderzył mnie tak silnie przez swe podobieństwo do kopca w Krakowie, usypanego na grobie bohatera narodowego Kościuszki, że choć w cudzym kraju, na cudzej ziemi, ale wśród ludu ceniącego wolność i jej obrońców, nie mogłem powstrzymać się od tego, żeby nie nadać temu szczytowi nazwy Góra Kościuszki". Rozległy widok ze szczytu pozwolił odkrywcy ustalić położenie źródeł rzeki Murray, najdłuższej rzeki kontynentu, określić bieg jej dopływów i podjąć decyzję co do kierunku dalszego marszu na południe. Po przekroczeniu Gór Wododziałowych Strzelecki wkroczył do krainy nietkniętej stopą białego człowieka. Na cześć gubernatora Nowej Południowej Walii nazwał ją Gippsland (obecnie jest to wschodnia część stanu Wiktoria), nadał także nazwy wielu rzekom i jeziorom na tym obszarze. Ziemie te były niezwykle piękne, żyzne i bogate w surowce, dlatego w raporcie z wyprawy Strzelecki zachęcał do rozpoczęcia akcji osadniczej w tym rejonie. Polski podróżnik się nie mylił – obecnie to jeden z najbogatszych rejonów Australii. Gwoli sprawiedliwości trzeba stwierdzić, że część tych ziem zbadał kilka tygodni przed Polakiem szkocki podróżnik Angus McMillan, pracujący na zlecenie wielkich posiadaczy ziemskich zainteresowanych nowymi terenami. McMillan spóźnił się jednak z opublikowaniem sprawozdania, poza tym miało ono mniej dokładny i naukowy charakter niż prace Polaka i dlatego nadane przez niego nazwy w znacznej mierze się nie przyjęły.
Odkryty przez Strzeleckiego Gippsland miał także groźniejsze oblicze, o czym podróżnik przekonał się po przekroczeniu rzeki, którą nazwał Latrobe – dla uczczenia wicegubernatora kolonii Charlesa La Trobe'a. Górzysty teren poprzecinany głębokimi jarami i potokami oraz porośnięty kolczastymi krzewami, tzw. scrubem, stawał się coraz trudniejszy do przebycia. Wyprawa przedzierała się przez scrub 26 dni, pokonując dziennie 3–5 km. Pod koniec wyprawy zabrakło prowiantu i żywiono się mięsem upolowanych zwierząt, głównie koali. Strzelecki opisał ten trudny etap podróży w liście z Tasmanii do Adyny Turno z 1 sierpnia 1840 r.: „Wkrótce konie wierzchowe i juczne osłabły i trzeba było je zostawić. Moi przyjaciele i nasi ludzie, spieszeni i zmuszeni do niesienia na plecach swoich rzeczy, po paru dniach zostali doprowadzeni prawie do ostatecznego wyczerpania. Ja przeciwnie. Z przyzwyczajenia skromny i powściągliwy w jedzeniu i piciu, mając za sobą przed tą wyprawą 3000 mil przebytych na piechotę z ciężarem o wadze 45 funtów na plecach, nie odczułem za bardzo zmęczenia i słabości. Wreszcie po tysiącznych niebezpieczeństwach, gdzie groziło mi, że ich utracę, spodobało się Opatrzności, że ich doprowadziłem do Port Phillip (...) żywych, ale podobnych do szkieletów. Ja również wyglądałem jak szkielet, okryty łachmanami, prawie bez spodni i butów". 19 maja 1840 r. wycieńczeni uczestnicy wyprawy dotarli do Melbourne, które było wtedy jeszcze małą osadą. Strzelecki spędził tam 41 dni, przygotowując szczegółowy raport z wyprawy i mapę Gippslandu.
Kolejnym australijskim przystankiem Strzeleckiego była Tasmania, zwana wtedy Ziemią Van Diemena. Polski badacz spędził na wyspie przeszło dwa lata, organizując trzy wyprawy w głąb lądu i pracując w swoim laboratorium badawczym w Launceston. Podczas poszukiwań geologicznych Polak odkrył i opisał kilka pokładów węgla, ponadto w okręgu Sorell koło Asbestos Range (obecnie Narawntapu) znalazł pokłady miedzi i złotonośnego kwarcu. W grudniu 1841 r. wziął jeszcze udział w morskiej wyprawie, której celem było zbadanie wysp w Cieśninie Bassa. Kapitan okrętu, którym podróżował Strzelecki, Lort Stokes, nazwał jego imieniem szczyt górujący nad Wyspą Flindersa. Strzelecki jako pierwszy wysunął także tezę, która później znalazła potwierdzenie w nauce, że góry Tasmanii są kontynuacją Gór Wododziałowych, co świadczy o tym, że wyspa była niegdyś częścią kontynentu.
Po zakończeniu badań terenowych na Tasmanii Strzelecki wrócił do Sydney, gdzie zabrał się do przygotowania gigantycznej (7,5 x 1,5 m) mapy geologicznej odkrytych przez siebie terenów i porządkowania zapisków z wypraw. Kiedy praca przy biurku go zmęczyła, zorganizował trzecią ekspedycję australijską, tym razem na północ, w trakcie której dotarł do najbardziej wysuniętych na północ farm Nowej Południowej Walii. Jak obliczył biograf Strzeleckiego Lech Paszkowski, polski podróżnik przemierzył na kontynencie australijskim przeszło 11 tys. km, co kosztowało ponad 5 tys. funtów, które zresztą wyłożył z własnej kieszeni. Głównym źródłem jego dochodów była sprzedaż okazów zoologicznych i geologicznych do muzeów europejskich.