Обойдя стороной прибрежные районы, населенные воинственными туземными, племенами, беглецы пересекли плоские равнины Техаса, страдая от палящего солнца и жажды. Они питались плодами опунций, утолявшими их голод и жажду. Прерии и плато, по которым они шли, были очень мало населены. Здесь кочевали небольшие племена индейцев, скудный скарб которых, привязанный к шестам, тащили огромные собаки. Дружелюбные и услужливые туземцы ничего не знали о злодеяниях белых пришельцев и радушно принимали беглецов, приветствуя их как сыновей солнца. Кавеса де Вака – прославленный знахарь и колдун в каждом селении лечил больных. Однажды ему якобы даже удалось вернуть к жизни умершего.
Беглецы были первыми из европейцев, увидевшими в прериях бизонов. Кавеса де Вака писал о них, что это темно-бурые или черные коровы с горбом на спине, короткими рогами и густой шерстью; мясо их сочное, жирное и более вкусное, нежели мясо испанских быков.
Этой горстке испанцев неплохо жилось среди индейцев, и они продвигались все дальше на запад, надеясь достичь побережья Великого Южного моря – Тихого океана. Оттуда легко было бы найти обратный путь в Мексику. По необъятным плодородным долинам Аризоны испанцы добрались до индейцев племени хопи, обладавших довольно Высокой культурой. Они занимались возделыванием земли, искусно изготовляли глиняную утварь и ткани, жили в глинобитных домах, которые лепили на крутых скалистых склонах, уступами один над другим.
С тех пор как экспедиция Нарваэса высадилась на берег Флориды, прошло уже восемь лет. И вот Кавеса де Вака, пройдя со своими спутниками через весь материк, в 1536 году достиг Калифорнийского залива. Там они встретились с белыми охотниками за рабами. Скитания Ваки по продолжительности и богатству приключений можно сравнить лишь со странствованиями Одиссея.
По возвращении в цивилизованный мир, Кавеса де Вака начал рассказывать о своих скитаниях всякие небылицы. И хотя он не видел ни золота, ни богатых городов, он все чаще и чаще намекал на то, что ему якобы попадалось такое, о чем он не смеет сказать ни слова. Превознося богатство и значение индейских селений, он говорил, что это якобы сказочные города с четырех- и пятиэтажными домами, двери и ворота которых украшены бирюзою, окна – алмазами, а золота там видимо-невидимо. Правители едят на золотых блюдах, пьют из золотых кубков, и таких городов целых семь, а страна эта зовется Сиволой. Так расписывал Вака «пуэбло» – нищие селения индейцев Аризоны и Новой Мексики.
В 1537 году Кавеса де Вака возвратился в Испанию и был принят самим Карлом V. Король с интересом выслушал знатного скитальца и в награду присвоил ему звучный титул «великий воин», а также разрешил предпринять новую экспедицию, чем впоследствии Вака и воспользовался.
В 1541 году он с отрядом в четыреста человек высадился на берег Южной Бразилии (27° 30' южной широты) и направился через горы в глубь материка. Наученный горьким опытом экспедиции Нарваэса, он поддерживал с индейцами дружественные отношения и достиг Асунсьона – испанской колонии на реке Паране, где занял пост губернатора. В этой продолжительной экспедиции Вака не потерял почти ни одного человека – редчайший случай в истории конкисты, как отмечает советский историк географических открытий И. Магидович. Однако Ваке не повезло в другом отношении: он и на сей раз не обнаружил в открытых им странах никаких богатств; соперники Ваки, домогаясь власти, вскоре арестовали его и выслали в Испанию.
Городами Сиволы, так ярко описанными Вакой, заинтересовался вице-король Новой Испании Мендоса. Он купил негра Эстевана, которого после долгих скитаний все же не отпустили на свободу, и снова послал его на север вместе с монахом-францисканцем братом Марком. Сопровождали их индейцы.
Эстеван, как в свое время Вака, разукрасился пестрыми перьями, бубенчиками и погремушками и занялся врачеванием и колдовством, исцеляя больных заговором. Он имел огромный успех. Туземные племена, встречавшиеся на пути экспедиции, принимали знаменитого кудесника как посланца небес. Ему приносили богатые дары, отводили самую лучшую хижину, украшали ее гирляндами цветов. Туземцы толпами валили к нему, стремясь хотя бы коснуться его одежды.
Эстеван больше не чувствовал себя рабом. Он путешествовал с целой свитой преданных ему индейских воинов и женщин, подаренных колдуну касиками. Индейцы были в восторге от его черной кожи и курчавой бороды. Безо всякого стеснения он прибирал к рукам наиболее дорогие подарки, в первую очередь бирюзу, приводя этим в негодование монаха Марка.
Экспедиция поднялась по долине реки Соноры и, перевалив через горы, вышла к Аризоне. Эстеван, снова услышав здесь о стране Сиволе и ее семи золотых городах, решил пойти на разведку.