В столице Новой Испании, как тогда называли сегодняшнюю Мексику, Кабеса де Вака, Дорантес и Кастильо проводят первое время в качестве гостей вице-короля Антонио Уртадо де Мендоса, встречаются с его самыми богатыми и знатными жителями, среди которых и сам первооткрыватель и завоеватель империи Монтесумы Эрнан Кортес, получивший к тому времени пышный титул маркиза дель Валье де Осака. Пробыв целых два месяца в Мехико, трое героев экспедиции Нарваэса отправляются в Испанию, а Эстебан, став давно свободным человеком, остается в новых землях и уже в 1539 году нанимается проводником экспедиции, которую еще до Коронадо в поисках Семи городов Сиболы организует монах Маркое Во время этого похода черный испанец будет убит индейцами племени суньи, которые, никогда не видев черного человека, приняли его за шпиона враждовавшего с ними племени.
Сначала дон Альваро и двое его спутников отправляются в порт Веракрус, где он садится на корабль, направлявшийся в Испанию. С немалыми морскими приключениями после остановок на Кубе и Бермудских островах, и едва спасшись от французских пиратов около Азорских островов, 9 августа 1537 года Кабеса де Вака прибывает в Лиссабон, а затем в свою любимую Севилью, откуда 10 лет назад он начал свою фантастическую и опасную авантюру. Здесь, в Севилье, он встречает героя походов в Центральной Америке и одного из конкистадоров Перу Эрнан де Сото. В результате завоеваний в Америке де Сото становится одним из самых богатых людей Испании и приближенным короля. Он с восторгом слушает рассказы дона Альваро о его перипетиях в Северной Америке и загорается жаждой сделать то, что не удалось Понсе де Леону, Айолосу и Панфило Нарваэсу. Кастильо и Дорантес, пробыв некоторое время в родной Испании, не смогли устоять перед соблазном снова поискать счастья в Америке. Они принимают решение вернуться в Мексику, где оба становятся богатыми людьми и остаются там жить спокойной жизнью новых поселенцев.
Самому Кабесе де Вака тоже уготована новая заокеанская миссия. Его слава знатока Индий, а также репутация честного и смелого аристократа побуждает императора Карла V поставить его во главе армады, которую он хочет послать вслед за экспедицией аделантадо[6] Педро Мендосы, столкнувшейся с очень большими трудностями в завоевании земель в бассейнах рек Ла-Плата[7] и Парагвай[8]. Вместо погибшего в ходе экспедиции Педро Мендосы император назначает дона Альваро на его место с титулом губернатора и аделантадо с задачей оказать помощь испанскому поселению в Буэнос-Айресе, основанному его предшественником, навести порядок в Асунсьоне, где бесчинствовали его управляющие, и осуществить дальнейшее завоевание земель вверх по течению рек Парана и Парагвай.
Следуя своему твердому принципу и опыту жизни среди обитателей новых земель, дон Альваро сразу же установил дружественные отношения с индейцами острова и на близлежащем побережье континента. Благодаря гуманному обращению с ними ему скоро стало известно от них, что где-то в 15 лигах от острова на континенте находились два монаха-францисканца, которых он сразу же вызвал к себе, чтобы узнать о том положении, которое сложилось в землях, граничивших с бассейном Ла-Платы. Эти монахи сообщили ему также, что из-за бесчинств испанцев в тех краях индейцы расправились с некоторыми из поселенцев, угрожая покончить и с остальными. Новому аделантадо довольно скоро удалось наладить мир с восставшими индейцами в этих местах и перейти к следующей задаче: выяснить, что происходит в Буэнос-Айресе на берегу Ла-Платы. В мае 1541 года, или через месяц после прибытия на Святую Каталину, Кабеса де Вака отправляет одну каравеллу в поселение, основанное Педро Мендосой, но из-за плохой продолжительной погоды и сильного встречного течения войти в русло Ла-Платы ей не удается, и она возвращается на остров. Вскоре туда же попадают девять испанцев, сбежавших из Буэнос-Айреса на лодке, где они не выдержали самоуправства оставшихся там власть предержащих. Услышав об испанском присутствии на Санта-Катарине, они решили искать убежища у аделантадо новой экспедиции. Прибывшие люди сообщили, что в Буэнос-Айресе по-прежнему оставались немногие жители, а также имелись некоторые запасы продовольствия. От них Кабеса де Бака узнал также, что Хуан де Айолас, которого Педро Мендоса отправил на открытие новых земель в район реки Парагвай, при возвращении из похода за оставленными на ней бригантинами, был убит вместе со всеми своими спутниками напавшими на них индейцами из племени пайягваес. От этого побоища удалось спастись только одному принявшему христианство индейцу, который и рассказал о происшедшей с Айоласом и его людьми трагедией. Он сообщил в том числе и о том, что командующий бригантинами Доминго де Ирала преднамеренно увел корабли до возвращения Айоласа, рассчитывая на его смерть от рук враждебных индейцев, с тем чтобы таким образом занять его место.
Прибывшие из Буэнос-Айреса испанцы поведали и о том, что многие из его бывших обитателей перебрались в более безопасный и обеспеченный новый город Асунсьон, находящийся на расстоянии свыше 350 лиг вверх по реке Парагвай. Там власть в свои руки взял тот же Ирала, творивший самоуправство по всей территории.
На основе полученных сведений дон Альваро решает направить каравеллы в Асунсьон через Буэнос-Айрес по рекам, а самому двигаться к нему по суше через широкие и неизведанные пространства южной части Бразилии. Для установления наиболее подходящего маршрута сухопутной части экспедиции губернатор отправляет отряд во главе с Педро Дорантесом. После трех месяцев отсутствия Дорантес вернулся с подробным отчетом о тех землях и племенах индейцев, которые находились на его пути и по которому предстояло пройти Кабесе де Бака и его людям.
В соответствии с проведенной подготовкой 18 октября 1541 года отряд дона Альваро с 26 лошадьми начинает свой долгий и многотрудный путь по территориям, которые до того времени не были известны европейцам. Оставшиеся на острове каравеллы во главе с племянником аделантадо Педро Кабесой де Вака и 140 людьми стали готовиться к своему походу в Асунсьон водным путем.
В течение 19 дней экспедиция губернатора с большими трудностями медленно двигалась в невыносимой жаре через непроходимые леса, большие горы и высокие холмы, буквально прорубая путь сквозь сплошные заросли, так как в этих землях не было никакого населения и никаких дорог или троп. Взятые с собой продукты постепенно начали портиться и истощаться, а затем и просто кончились. Окружающая природа была для европейцев незнакомой и враждебной. Они постоянно были опасались неожиданного нападения хищных зверей, укусов змей или насекомых. Плоды незнакомых растений есть остерегались, не зная, могут или нет они вызвать отравление. На их счастье, к концу этого срока им встретилась наконец первая индейская деревня, где очень дружелюбно настроенные индейцы, удивленные появлением среди них белых людей, которых они никогда раньше не видели, буквально задарили их разными продуктами питания. Зная по собственному большому опыту, что дружба с индейцами в новых землях может обеспечить спасение его экспедиции и помощь в противодействии возможным враждебным племенам, аделантадо приказывает своим людям не только всегда оплачивать получаемые от них продукты и предметы обменным товаром, но и особо одаривать подарками их вождей и старейшин.
