Во время этих экспедиций Перси Фосетт — или, как называл его в своем дневнике его сын Джек, «отец» — вступал в контакт с десятками индейских племен, которые еще никогда не видели белого человека и даже не слышали о нем. Большинство из этих неведомых племен были миролюбивыми, гостеприимными и довольно хорошо развитыми в социальном отношении, но, тем не менее, встречались и такие племена, которые находились еще на уровне каменного века, и, поскольку у этих дикарей еще сохранялись традиции каннибализма, их лишь с большой натяжкой можно было назвать людьми.
Однако наиболее значительную роль в жизни Перси Фосетта (а следовательно, в жизни его сына Джека и его друга Рэли) сыграли ходившие по бассейну реки Амазонки легенды, в которых рассказывалось о мифическом государстве, якобы созданном расой полубогов, называемых «древними людьми», и об их затерявшемся в джунглях сказочном городе, которому полковник почему-то дал странное название, состоящее всего лишь из одной латинской буквы «Z».
Во время каждого из своих путешествий Перси Фосетт записывал все больше и больше легенд, повествующих об истории и судьбе этого мифического государства, и, соответственно, росло его желание найти доказательства, которые подтверждали бы его существование. Одно из таких доказательств он в конце концов нашел в Национальной библиотеке в Рио-де-Жанейро, обнаружив там рукопись, которую подписал священник Х. де ла К. Барбоса и в которой рассказывалось об удивительном путешествии некоего Франсиско Рапозо по территории бразильского штата Мату-Гросу. В рукописи, в частности, сообщалось, что Франсиско Рапозо, ведя группу из восемнадцати переселенцев через сельву в поисках плодородных земель, на которых можно было бы обосноваться, пересек горы, болота и различные реки и прибыл на берега реки Шингу. Встретившись там с враждебно настроенными индейцами и пытаясь спастись от них бегством, он и его спутники натолкнулись на большой заброшенный город, чем-то похожий на крепость инков Саксайуаман.
Этого было вполне достаточно для того, чтобы Перси Фосетт уверился в реальности существования города Z (если полковник к тому моменту еще не был в ней уверен), а потому он, руководствуясь весьма скудными сведениями, имеющимися в рукописи, решил немедленно отправиться на поиски города, планируя взять с собой только Рэли и своего сына Джека — молодых, сильных и преисполненных энтузиазма людей. Он продал эксклюзивное право на опубликование информации о его будущем открытии одному американскому журналу и, используя деньги, которые он получил от этого журнала и сумел выпросить у некоторых географических обществ, быстренько организовал экспедицию. В начале 1925 года он, его сын Джек и Рэли вышли из бразильского города Куяба, находящегося неподалеку от боливийской границы, на восьми мулах, с шестью носильщиками и двумя псами — Пастором и Чулимом.
Страницы дневника, посвященные первым неделям путешествия, были так сильно повреждены, что прочесть на них что-нибудь оказалось попросту невозможно. Первая последующая запись, которую мы смогли понять, была датирована 29 мая 1925 года и содержала следующие сведения:
«Сегодня мы покинули лагерь, который отец называет Лагерем мертвой лошади, потому что во время предыдущей экспедиции он потерял здесь лошадь: ее укусила ядовитая змея. Эти два дня отдыха пришлись нам как нельзя кстати, потому что переход из Куябы до этих мест был долгим и изнурительным. Кому в нашей цивилизованной Англии могло бы прийти в голову, что на то, чтобы пройти немногим более двухсот миль по джунглям, уйдет почти два месяца!..У Рэли дела с ногой уже получше, хотя от заражения, вызванного укусами клещей, избавиться пока не удалось и он все еще хромает, однако он сильный, и у меня нет никаких сомнений, что он поправится. Отец по-прежнему крепок как дуб. Хотя он более чем в два раза старше меня и заметно похудел с того момента, как мы отправились в путь, он ни на капельку не снижал темпа нашего движения, и его глаза всегда светятся энтузиазмом.
Сегодня мы распрощались с носильщиками, передав им письма для наших родственников, и остались с шестью мулами и двумя собаками, поскольку отец не хочет, чтобы кто-то еще знал о том, куда мы направляемся. Начиная с этого момента мы будем идти там, где еще не ступала нога ни одного белого человека, и откроем места, о которых всему остальному человечеству еще ничего не известно. Именно сейчас начинаются настоящие приключения. И да поможет нам Господь».