Во время одного из своих торговых странствий он узнает от нескольких индейцев, что в двух днях пути от них в плену у другого индейского племени находятся двое белых и один черный испанец. С помощью дружественных индейцев дон Альваро тайно и под покровом ночи встречается со своими друзьями, и они договариваются о совместном побеге через шесть месяцев в период созревания диких груш, орехов и других лесных плодов, которыми они могли бы питаться на протяжении своего длительного пути. В условленное время все четверо собираются вместе и отправляются на запад в поисках спасения из многолетнего плена. Это произошло в августе 1535 года.
В поисках убежища и пропитания среди незнакомых им племен четверка испанцев выдает себя за врачевателей, пользуясь уже ранее зарекомендовавшими себя методами. Слава опережает их собственное продвижение. Жители очередной деревни провожают их до следующей. Таким способом, двигаясь витиеватыми путями и меняя направление в зависимости от ландшафта местности и расположения индейских поселений, решительная четверка испанцев стала первыми европейцами, которые прошли пешком огромные пространства сегодняшних Техаса, Новой Мексики, Аризоны и Северной Мексики. «Весь этот путь, — писал впоследствии дон Альваро, — через всю эту территорию мы прошли голыми, меняя подобно змеям нашу кожу два раза в год». Уже на территории Мексики, о чем им самим еще было неизвестно, путешественники встречаются с индейцами, которые занимаются сельским хозяйством, выращивая бобы, кукурузу, хлопок и прочие культуры. Здесь они получают повязки из хлопка, чтобы прикрыть свою наготу.
После еще многих дней нелегкого пути в одной из деревень спутники встречают индейца, который носит как украшение рукоятку меча и гвоздь. В ответ на их вопрос, откуда у него эти предметы, индеец показывает в сторону недалекого моря и объясняет, что подобрал их в западной стороне на земле после того, как там проехали люди в латах. Это было первым признаком недавнего присутствия в тех краях испанцев. Испытанная от такой долгожданной новости радость переполняет сердца и поднимает силы утомленных многолетними скитаниями людей. Охваченные душевным подъемом, они вновь бросаются в дорогу, все чаще и чаще встречая предметы, свидетельствующие о недалеком нахождении их соотечественников. Сейчас их путь проходил по территории будущего мексиканского штата Сонора Здесь же неутомимая четверка сталкивается с другой огорчающей их стороной присутствия испанцев: пустующие деревни индейцев, которые были покинуты ими в поисках спасения от преследования в горах. С большой горечью и негодованием пишет дон Альваро о бесчинствах своих соотечественников: «Картина, явившаяся нашему взору, вызвала в нас чувство бескрайней боли: плодороднейшая и прекрасная земля с многочисленными реками и источниками покрыта сожженными и брошенными деревнями, а исхудалые ее жители превращены в беженцев, ищущих спасения и убежища».
Кабеса де Вака и его спутники продолжают двигаться вперед. Пройдя еще около 10 лиг, они вдруг встречают четырех вооруженных всадников. Осадив коней перед грязными, опаленными солнцем и завернутыми в грубые шкуры людьми, они, не веря своим ушам, вдруг слышат прекрасную испанскую речь. Представившись, старший альгуасил и королевский казначей экспедиции Панфило Нарваэса просит отвести его в штаб командующего войсками этой местности. Капитан Диего де Алькасар, перед которым вскоре предстал Кабеса де Вака, встретил его с неподдельным восторгом, а затем приказал привести Кастильо и Дорантеса Негр Эстебан официально числился рабом Дорантеса и не мог быть приглашен вместе с хозяином к капитану. Верный своему долгу дон Альваро сразу же попросил пригласить к себе писаря, которому немедленно надиктовал свой первый рапорт о судьбе экспедиции Нарваэса Для кабальеро Кабесы де Бака наконец остались позади 8 лет невероятных опасных скитаний, 5 лет рабства в полном одиночестве среди диких индейских племен, около 450 погибших соотечественников и почти 3 тысячи пройденных пешком очень трудных невероятных лиг. Дав им немного отдохнуть, капитан Алькасар пересылает четверку свалившихся на него «диких» соотечественников в город Компостела местному губернатору, который предоставил им одежду и кровати. Однако после стольких лет хождений в голом виде и приобретенной привычке спать на земле, как сообщает дон Альваро, он и его товарищи «в течение некоторого времени не могли носить одежду, а спать могли только на земле». Вслед за коротким пребыванием в гостях у губернатора в Компостеле трех путешественников без Эстебана направили в Мехико — столицу Новой Испании, куда они прибыли 25 июля 1536 года, то есть почти 8 лет спустя после их кораблекрушения у острова Несчастий.
Они — Кабеса де Бака, Дорантес и Кастильо — стали единственными оставшимися в живых из тех 600 человек, которые более 9 лет до этого составляли самую крупную на то время экспедицию, направлявшуюся в Новый Свет. Трагедия этой очередной безуспешной попытки завоевать огромную территорию Флориды и завладеть ее воображаемыми богатствами не только не остановила новых авантюристов, жаждущих славы, наживы и приключений, но и послужила толчком для организации и проведения целой серии последующих экспедиций уже вскоре после возвращения к цивилизации удивительно счастливой четверки. В немалой степени этому возрожденному интересу к раскрытию манящей тайны северной части Американского континента способствовали сами выжившие участники трагедии, постигшей экспедицию Нарваэса. Рассказывая многим из своих слушателей об увиденном и пережитом ими за 8 долгих лет опасных скитаний и мучительных перипетий по прибрежной полосе Мексиканского залива, а также глубинных земель Техаса, Аризоны и северной части Мексики, они свидетельствовали как побывавшие там люди о почти первобытном существовании их жителей и об отсутствии в них богатых цивилизаций. Полагаясь, однако, на старые и услышанные ими от индейцев новые легенды о существовании где-то в тех же краях Семи сказочных городов Сиболы, в которых им не довелось побывать во время выпавших на их долю скитаний, они повторяли и обогащали уже бытовавшие среди испанцев мифы об этих землях. Они делали это с тем большей убедительностью, поскольку сами считали, что были рядом с этими местами и сами твердо верили в их существование. Среди тех, кто жадно внимал рассказам Кабесы де Бака и его товарищей были и честолюбивый вице-король Антонио Мендоса, и конкистадор Мексики Кортес, и будущий завоеватель больших новых земель Васкес де Коронадо, и уже участвовавший во многих успешных экспедициях Эрнан де Сото, да и другие, кто вскоре начнут готовиться и отправляться в поисках легендарных царств, городов и земель обширной территории юго-запада сегодняшних Соединенных Штатов Америки. Васкес де Коронадо уже через некоторое время поспешит в собственную длительную экспедицию. Смело углубившись в земли континента, но не найдя там сказочных Семи городов Сиболы, он откроет миру Великий каньон, Канзас, Арканзас, обследует русло реки Колорадо, пройдет тысячи миль по неизведанным землям и значительно расширит владения Испании в Северной Америке. Эрнан де Сото с большим отрядом пройдет по суше от полуострова Флорида до Арканзаса и станет первым европейцем, который откроет русло Миссисипи. Рассказы дона Альваро и его спутников будут широко передаваться из уст в уста по всем испанским владениям и на самом Пиренейском полуострове, разжигая воображение новых авантюристов и привлекая растущие ряды желающих искать свое счастье там, куда не смогли пройти Нарваэс и его люди…
