Фосетт получил напутствие от Джека, писавшего, что когда-то его посетило «сновидение», в котором он входил в храм древнего города наподобие Z. Джек надеялся, что «на всех этапах своего странствия» отец будет «под защитой», и желал ему счастливого пути. Местного жителя, выбранного им в качестве посредника, Фосетт попросил: в случае, если его родные или друзья «начнут волноваться, не получая от меня вестей, пожалуйста, успокойте их твердым заверением, что наш путь не может окончиться нежелательным образом и что в ходе маршрута мы непременно будем посылать о себе известия». В письме к Келти он поклялся: «Я собираюсь достигнуть этого места и вернуться обратно». Затем, в сопровождении двух своих спутников, двух лошадей, двух волов и пары собак, он отправился на север, в сторону реки Шингу, сжимая мачете, как рыцарь сжимает свой меч.
Но вскоре все пошло наперекосяк. Ливни затопили их путь и привели в негодность снаряжение. С Брауном, несмотря на его непобедимо-свирепый вид, случился нервный срыв, и Фосетт, опасаясь новой катастрофы а-ля Мюррей, отправил его назад в Куябу. Холт также расклеивался все больше: он заявлял, что полевые исследования в таких чудовищных условиях проводить невозможно, и с маниакальной тщательностью каталогизировал всех насекомых, нападавших на него, так что в конце концов в его дневнике уже не появлялось больше никаких других сведений. «Серьезно болен из-за насекомых, — выводил он, добавляя: — Дни тяжкого труда, ночи тяжких мучений — вот она, жизнь путешественника! А где же романтика?»
Фосетт впал в ярость. Как ему добраться куда бы то ни было с «этим калекой»? — вопрошает он в своих путевых заметках. Но и сам Фосетт, которому было уже пятьдесят три, теперь утратил неуязвимость по отношению к силам природы. Его нога распухла, в нее попала инфекция. «Меня уже давно тревожит больная нога, особенно сильно по ночам, так что я почти не мог спать», — признается он в дневнике. Однажды ночью он принял пилюли опиума и тяжело заболел. «Слечь в постель — для меня чрезвычайное происшествие, и мне было страшно стыдно за самого себя», — пишет он.
Прошел месяц после начала путешествия, и животные начали сдавать. «Это ужасно, ничьи нервы не выдержат, когда смотришь, как вьючная скотина медленно умирает», — писал Холт. Вол, тело которого кишело личинками, лег и больше не поднялся. Одна из собак стала умирать с голода, и Холт пристрелил ее. Утонула лошадь. Потом другая лошадь упала на ходу, и Фосетт положил конец ее мучениям с помощью пули: это было как раз в том месте, которое позже стали называть Лагерем мертвой лошади. Наконец Холт распростерся на земле и провозгласил: «Не обращайте на меня внимания, полковник, идите дальше и оставьте меня здесь умирать!»
Фосетт знал, что эта экспедиция может стать для него последним шансом доказать его теорию о Z, и он проклял богов за то, что они сговорились против него: он бранил их за погоду, за своих спутников, за войну, которая так его задержала. Фосетт понимал, что, брось он Холта, тот умрет. «Оставалось лишь вернуться с ним обратно, — позже писал Фосетт, — и признать, что экспедиция провалилась самым досадным образом».
Чего ему не хотелось признавать, так это того, что его собственная зараженная нога сделала продвижение вперед почти невозможным. Когда отряд мучительно пробирался обратно, к ближайшему форпосту на фронтире, на протяжении тридцати шести часов страдая без воды, Фосетт заметил Холту: «Выходить из ада всегда трудно».
Когда они объявились в Куябе в январе 1921 года, посол Пейджет отправил Нине телеграмму, в которой говорилось лишь: «Ваш муж вернулся». Нина спрашивала у Гарольда Ларджа: «Как вы думаете, что это означает? Мне кажется, все-таки не поражение! Может быть, он и не нашел „затерянные города“, но я думаю, что он наверняка обнаружил что-нибудь важное, а то он бы ни за что не вернулся». Тем не менее пришел он ни с чем. Генерал Рондон выпустил злорадное заявление для прессы, где сообщалось: «Экспедиция полковника Фосетта прекращена… несмотря на все самолюбие путешественника… Он вернулся отощавшим, понятным образом разочарованный тем, что вынужден был отступить, даже еще не войдя в сложнейший для передвижения район Шингу». Совершенно уничтоженный, Фосетт начал строить планы возвращения в джунгли вместе с Холтом: контракт с ним оставался в силе, к тому же Фосетт больше не мог позволить себе ничьи услуги в своем нынешнем финансовом положении. Супруга американского вице-консула в Рио, которая дружила с женой орнитолога, послала Холту письмо, заклиная его не идти: