По прибытии в Австралию он работал землемером, выделял поселенцам наделы земли в пустынных районах континента. Тогда он и научился любить удаленные районы Центральной Австралии.
Кроме того, Стюарт развил в себе отличные навыки выживания в экстремальных условиях. В результате британский путешественник капитан Чарльз Стёрт предложил ему присоединиться к своей экспедиции в центр континента в 1844 году.
В планах исследователей новых земель было изучить Новый Южный Уэльс и двинуться дальше в глубь страны. Их немногочисленной команде удалось выполнить намеченное, но урон здоровью был нанесен весьма значительный. Капитан Стёрт страдал от цинги, а к концу экспедиции почти ослеп. К счастью, с ним был Стюарт, получивший возможность продемонстрировать на местности все знания, которыми обладал в достатке.
Однако он также не уберегся от цинги, не говоря уже о язвах на теле и авитаминозе — ужасном заболевании, способном вызвать рвоту, паралич и ухудшение психического состояния. По окончании экспедиции Стюарт настолько исхудал, что сквозь кожу буквально проступали кости, десны кровоточили, зубы выпадали, а мышцы атрофировались. Несколько месяцев он был прикован к постели, и врачи не были уверены, что ему удастся выжить.
Казалось бы, подобный опыт должен навсегда отбить охоту к исследованиям и путешествиям. Но нет.
Стюарт полюбил австралийский бушленд. Там, где остальные видели лишь пустыню, покрытую редким кустарником, он видел много большее: стаи птиц, разломы в горной породе, которые могут привести к драгоценной воде. Он научился мастерить шалаш из австралийского эвкалипта, ориентироваться на местности, используя компас и подсказки природы. Стал необыкновенно чувствительным к едва заметным изменениям в пейзаже.
Создавалось впечатление его единения с этой суровой средой.
Шли месяцы и годы, а Стюарт проводил больше времени в бушленде, нежели в городах. В мае 1858 года, в возрасте 42 лет, он организовал первую собственную экспедицию. В планах было исследовать местность за шахтой Оратунга в горах Флиндерс в Южной Австралии, куда никогда не ступала нога белого человека.
Примерно в это время исследователь по имени Бенджамин Гершель Бэббидж готовился к такой же, но гораздо лучше финансируемой экспедиции. Бэббидж и его люди взяли с собой такую роскошь, как 20 килограммов шоколада, 38 килограммов немецкой колбасы, 150 овец и холодильник с 22 литрами питьевой воды.
У несгибаемого, измученного непогодой Стюарта и двух его компаньонов имелось шесть лошадей, компас и запас самых простых продуктов на четыре недели.
С таким снаряжением экспедиция Стюарта направилась в бушленд. Они дошли до огромного соленого озера — ныне известного как озеро Торренс — шириной до 200 и длиной 30 километров. От высокой температуры раскалялась земля, а в округе не было ни одного источника воды.
По пути им попался один из членов команды Бэббиджа.
Он был мертв, и коричневого цвета кожа была натянута на скелете, как на барабане.
Мучимый жаждой, он перерезал горло трех вьючных лошадей, чтобы выпить их кровь.
Весь ужас его положения в последние минуты перед гибелью выражался в нацарапанных на жестяной фляге словах: «Мои глаза слепнут. Язык горит. Выхода нет. Господи, помоги, я не могу подняться…»
Эти места высасывали жизнь из тех, кто был недостаточно вынослив, чтобы все выдержать.
Стюарт провел в том районе четыре месяца. Он прошел 2400 километров. Неудивительно, что, вернувшись к цивилизации, он обрел репутацию лучшего исследователя эпохи.
Но правда состояла в том, что он еще даже не приступил к исполнению задуманного.
Впрочем, Стюарт был таким же стойким и закаленным погодными условиями, как и окружавшая его местность. Он, безусловно, не был джентльменом и любил вкус крепкого рома.
В одном дневнике встречаются такие воспоминания о нем: «Он был самым гнусным пьяницей и самым грязным человеком из всех, кого я когда-либо встречал». Или же вот слова четырнадцатилетнего мальчика, знавшего Стюарта: «Такой смешной маленький человек, всегда пьяный… вернувшись из долгого путешествия, он заперся в комнате и пил три дня кряду».
Его считали сумасшедшим — постепенно идущим к безумию, — но очевидно, что Стюарта мало волновало мнение о нем окружающих. Он избегал общества. Избегал толпы. Он был человеком жившим, чтобы исследовать.
В то время юг Австралии был полностью отрезан от северного побережья. По континенту не были проложены дороги, не было и телеграфных проводов.