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