Покинув свой лагерь Ауте экспедиция блуждала более тридцати дней по бухтам, островкам и лиманам, испытывая ужасный голод, страшную жару и постоянные страхи перед волнениями моря. В ожидании улучшения погоды им приходилось проводить по несколько дней на берегу. Оказавшись затем в заливе Пенсакола, люди наконец обрели возможность передохнуть после своих морских злоключений, но при этом постоянно подвергались коварным нападениям местных индейцев, которые днем вели себя дружелюбно, а ночью не оставляли испанцев в покое, от чего многие из них получили ранения. Продвигаясь далее на запад вдоль побережья, в самом конце октября 1528 года флотилия измученных и совершенно обессилевших участников экспедиции успешно пересекла устье могучей реки, о чем они могли судить по пресной воде в море на значительном расстоянии от берега. Это было устье еще не знакомой им Миссисипи. Все пять судов пока еще держались вместе, но вдруг поднявшийся с берега сильный холодный ветер разделил их перед наступлением ночи. На следующее утро два баркаса бесследно пропали, а три оставшихся лодки стало сносить мощным течением реки все дальше в море.
Судно Нарваэса, в котором были самые сильные гребцы, стало обгонять и оставило позади лодки Кабесы де Вака и капитана Пеньалоса. В течение пяти дней оба отставших судна ценой огромных усилий экипажей успешно сопротивлялись вновь разбушевавшемуся морю, но затем лодка Пеньалосы вдруг неожиданно раскололась, и вся ее команда исчезла в бушующей пучине волн. С наступлением ночи море начало успокаиваться, и при свете появившейся луны Кабеса де Вака и его люди увидели перед собой узкую полосу земли. Вскоре обессилевший экипаж лодки с большим трудом выбрался на песчаный пляж его нового спасительного пристанища. Это было 8 ноября 1528 года.
Обследование местности показало, что испанцы оказались на острове. Здесь они скоро встретились с проживающими на нем мирными, но очень бедными индейцами, которые благоговейно помогали белым пришельцам, чем могли, приняв их за «особые существа». Пополнив запасы продовольствия с помощью индейцев, команда дона Альваро, в которой все, кроме пяти человек, были совершенно больны, решила снова сразу же отправиться в плавание, чтобы как можно скорее добраться до своих. Однако при попытке столкнуть лодку в воду, когда они сняли с себя все, что у них было, то есть одежду, оружие и продовольствие, и положили в нее, их судно перевернулось от сильной набежавшей волны. Трое человек утонули, погибло все, что находилось в лодке, а оставшимся в живых, голыми и промерзшими, удалось вернуться на берег. Местные индейцы снова оказали им первую помощь, а затем отвезли их в свою деревню. Там испанцы узнали, что на острове оказались другие белые бородачи, в которых они скоро опознали офицеров Андреса Дорантеса и Алонсо дель Кастильо и сопровождавших их людей. Они находились в одной из ранее пропавших лодок и выжили после прошедшей бури. Судно Нарваэса с его экипажем бесследно исчезло в морской стихии.
На этом острове, которым предположительно является техасский остров Гальвестон, 80 оставшихся в живых испанцев пробыли до мая нового 1529 года, но к этому времени их осталось всего 15 человек. Остальные умерли, не выдержав голода, ран и болезней. Гостеприимные индейцы сами жили в страшной нищете, но при этом они готовы были делиться с незваными пришельцами тем, что добывали для пропитания. Однако через некоторое время индейцы предложили испанцам «отрабатывать свой хлеб» в качестве целителей больных, что было связано также с возникшей (без всяких на то оснований) верой среди туземцев, что белые пришельцы из другого мира обладают магическим даром врачевания. Не имея другого выхода, испанцы дают согласие на это предложение и выбирают Кабесу де Вака, как самого образованного среди них, для оказания «помощи» первому больному в соседней деревне. Спросив, где больной испытывает боль, немало переживавший за исход дела дон Альваро, осенил больное место крестным знаменьем, подышал на него и, встав на колени, произнес молитву «Отче наш» с призывом ко Всевышнему излечить его пациента. Каково же было удивление индейцев и не в меньшей степени самих испанцев, когда после завершения этого обряда больной встал и радостно объявил, что он полностью здоров.
С тех пор авторитет дона Альваро и трех его товарищей по несчастью — Дорантеса, Кастильо и мавра Эстебана — как магических целителей распространился среди жителей всего острова и соседнего побережья Мексиканского залива. Как признается в своих описаниях этих событий сам Кабеса де Вака, крестное знаменье и молитвы были их единственным и безотказным методом врачевания индейцев. Однако, этот популярный магический дар не освобождал его обладателей от выполнения самого тяжелого труда для индейцев. Им приходилось переносить большие грузы, находить и заготавливать дрова, а также выполнять ряд других нелегких работ.
Однажды во время сбора орехов дон Альваро оказался среди индейцев соседнего племени, которые увели его с собой на континент в поисках пропитания. В итоге он разлучился со своими соотечественниками, оставшимися на острове, названном им «островом Несчастий». Все они стали настоящими рабами своих хозяев.
В самом тяжелом положении из этой четверки «врачевателей» оказался дон Альваро, который провел в полном одиночестве среди разных племен целых невероятных шесть лет. Немало раз за это время он оказывался по разным причинам на грани смерти, серьезно болел, страдал от отсутствия своих, не зная, что происходит с ними и что будет с ним. После очередного выздоровления Кабеса де Вака решает стать нейтральным торговцем-менялой между постоянно враждовавшими друг с другом индейскими племенами, перенося на себе нужные им примитивные товары: морские ракушки и улиток с берега моря в глубь территории, где из них изготовлялись разные режущие инструменты и предметы, а оттуда приносил кожи животных, острые камни для наконечников стрел и твердые стволы тростника для их изготовления и прочие вещи. Переходя от племени к племени и покрывая пешком большие расстояния, Кабеса де Вака хорошо узнает жизнь индейцев и их языки, становится знатоком местности, запоминает пути и тропы, которые могут пригодиться при осуществлении побега в испанские территории Мексики, о чем его никогда не покидает мысль.
Во время одного из своих торговых странствий он узнает от нескольких индейцев, что в двух днях пути от них в плену у другого индейского племени находятся двое белых и один черный испанец. С помощью дружественных индейцев дон Альваро тайно и под покровом ночи встречается со своими друзьями, и они договариваются о совместном побеге через шесть месяцев в период созревания диких груш, орехов и других лесных плодов, которыми они могли бы питаться на протяжении своего длительного пути. В условленное время все четверо собираются вместе и отправляются на запад в поисках спасения из многолетнего плена. Это произошло в августе 1535 года.
