Vilun, puutteen ja muitten kärsimysten vuoksi Cabezan ja Castillon miehet toinen toisensa jälkeen kuolivat, niin että lopulta vain neljä oli elossa, yksi näistä Cabeza, toinen Estebanico niminen neekeri, jonka myöhemmin tapaamme toisilla asioilla. Cabeza de Vaca oli rohkea ja neuvokas mies. Hän oppi intianien kielen ja perehtyi heidän tapoihinsa ja sitten saavutti vaikutusvaltaakin, koska hän muka taisi parantaa tauteja. Mutta aluksi oli seikkailijain kohtalo hyvin surkea. Intianit pitivät heitä orjinaan vuosikausia ja nöyryyttivät ja kiduttivat heitä monella tavalla. Monena iltana heidän rinnalleen laskettiin nuoleja sen merkiksi, että heidät aamulla tapettaisiin. Mutta he pääsivät vihdoin pakoon ja tapasivat toisia heimoja, jotka luulivat heidän taivaasta tulleen. Toiset toivat ruokansa heidän siunattavakseen, toiset kantoivat heidän eteensä parhaat tavaransa ja pyysivät heitä valitsemaan, mitä tahtoivat, ja toisinaan tuhannet saattelivat heitä matkalle. Cabeza tovereineen paranteli sairaita »Pater nosteria» lukien ja ristinmerkkiä tehden. He vaelsivat heimosta heimoon ja ansaitsivat elantonsa kaupittelemalla kaikenlaisia pieniä esineitä. Sitten he taas olivat jonkun aikaa eri heimoissa vankina, toisistaan erotettuina, mutta pääsivät uudelleen yhtymään Sabine-joen länsipuolella ja alkoivat vähitellen vaeltaa Tyyntä merta kohti sikäläisiin espanjalaisiin siirtokuntiin.
Cabezan kertomuksesta voimme jotenkin tarkkaan seurata hänen matkansa kulkua. He pyrkivät rannikolta sisämaahan, kuultuaan, että siellä asui taajemmassa ihmisiä ja lempeämpiä. Samalla he halusivat nähdä maata laajemmalta, voidakseen joskus laatia siitä kuvauksen. Halki nykyisen Texasin he kulkivat pohjoiseen aina Canadian-riverille, Arkansaan latvaosille saakka. Intianien polkuja seuraten he menivät vedenjakajan poikki ja tulivat Mexicon nykyisen rajajoen Rio Granden laaksoon. Samoin kuin intianeilla heilläkin oli sarvaannahkasta vaatteet, talvella puhvelinnahkasta. Rio Grandelta he hitaasti vaelsivat edelleen länttä kohti, poiketen intianikyliin, paljon vaaroja, puutetta ja vaivoja kärsien. Vihdoin he pääsivät Californian lahden rannalle nykyiseen Sonoraan, jossa silloin jo oli espanjalaisia siirtokuntia. Toukokuussa 1536 he näkivät Tyynen meren pinnan ja olivat kolmetuhatta kilometriä kuljettuaan vihdoinkin päässeet vaivainsa päähän. Yhdeksän vuotta oli kulunut siitä, kun he lähtivät Narvaezin kanssa Espanjasta. ja melkein kahdeksan vuotta siitä, kun he olivat Floridan rannoilta hatarilla veneillä retkensä jälkiosan alkaneet. Kuusi vuotta tästä ajasta olivat Texasin intianit heitä pitäneet vankeudessa. Kaksikymmentä kuukautta kului matkaan maan poikki Californian lahdelle. Cabeza de Vaca tovereineen oli ensimäinen. joka Mexicoa pohjoisempana kulki Pohjois-Amerikan poikki. Heitä oli jo aikoja sitten luultu kuolleiksi; sitä suurempi oli nyt riemu. Kunniavartiosto saattoi heitä Compostellaan ja pitkin matkaa heitä Mexicossa joka kaupungissa kestittiin yhteisinä vieraina.
Seuraavana vuonna Cabeza de Vaca palasi Espanjaan ja nimitettiin muutaman vuoden kuluttua Rio de la Plata maakunnan »adelantadoksi». Hän menomatkalla nousi maalle Brasilian rannalla Santa Catharine nimisen saaren luona ja kulki sieltä maan poikki Asuncioniin, Paranan ja Paraguayn yhtymäpaikalle, joka silloin vielä oli siirtokunnan pääkaupunki. Myöhemmin hän, välillä jo vuoden maanpaossakin vietettyään, nimitettiin Sevillaan tuomariksi ja kuoli v. 1564 vaiheilla. Molemmista suurista matkoistaan ja ihmeteltävistä seikkailuistaan Cabeza de Vaca kirjotti matkakertomukset.
Hernando de Soton retki Mississipin laaksoon.
Vaikka Narvaezin retki päättyikin näin onnettomasti, niin tehtiin vielä uusia yrityksiä samoihin maihin. V. 1538 Hernando de Soto, Pizarron etevimpiä upseereja Perun vallotuksessa, siellä melkoisen omaisuuden koottuaan sai Espanjan hallitukselta Cuban maaherruuden ja luvan lähteä Floridaa anastamaan. Soton suuri maine vaikutti, että hänen yritykseensä liittyi mitä loistavin joukko ritareita. Kymmenellä laivalla, mukanaan 900 miestä ja 350 hevosta, tykkejä, pyssyjä, verikoiria ja kahleita, hän v. 1538 purjehti Sevillan satamasta Cubaan ja sieltä iloisten juhlain jälkeen meren poikki Floridaan. Laivat lähetettiin takaisin Cubaan. jonka hallinnon Soto oli poissa olonsa ajaksi uskonut vaimolleen, Pedrarias Davilan tyttärelle. Soto vei väkensä maihin kesäkuussa 1539 ja lähti sitten tunkeutumaan sisämaahan. Siellä täällä oli melkoisia intianikyliä, mutta asukkaat olivat kauttaaltaan vihamielisiä. Lukuisat rämeet ehkäisivät niin suuren joukon kulkua. Eräänä päivänä Soton väki suuresti hämmästyen näki intianijoukon keskellä hevosella ratsastavan valkoisen miehen, joka hurjin ilonelkein lähestyi heitä ja tervehti heitä espanjan kielellä. Hän olikin espanjalainen, Juan Ortiz nimeltään, muuan Narvaezin miehistä, jonka intianit olivat vangiksi saaneet ja päällikön tytär kahdesti kuolemasta pelastanut. Ortiz oli vankeutensa ajalla oppinut intianien kieltä ja tutustunut heidän tapoihinsa; hänestä sai Soto hyvän tulkin. Mutta Ortiz ei tiennyt mitään niistä rikkauksista, joita siellä muka piti olla, sen mukaan kuin intianit olivat Sotolle uskotelleet; hänen kertomuksensa tosioloista masensi suuresti retkeläisiä, joiden kesken mieliala alkoi muutoinkin olla painuksissa. Sotoa vaadittiin palaamaan, mutta hän jäykästi ilmotti jatkavansa matkaa, kunnes oli omin silmin nähnyt maan köyhyyden.
Talvea vietettiin siinä lahdessa, joka on Floridan ja Alabaman välissä, Apalachee nimisessä maakunnassa. Ruokavaroja oli siellä kyllin, mutta turhaan etsittiin muita rikkauksia. Keväällä v. 1540 Soto samosi pohjoista kohti, lähettäen aina edellään tottuneita vakoojia maanasukkailta pyytämään vapaata kulkua. Muuan Intiani lupasi opastaa Soton «etäiseen, kuningattaren hallitsemaan maahan, jossa oli paljon keltaista metallia. Espanjalaiset lähtivät uusin toivein häntä seuraamaan, aavistamatta sitä, että metalli olikin vain halpaa vaskea. Kuningatar, joka oli erään heimon päällikkö, tuli kantotuolissa kaikkiin koruihinsa puettuna Sotoa vastaan. Nousten alas kantotuolista hän lähestyi ritaria, toivottaen hänet tervetulleeksi, ja heitti hänen kaulaansa kahdenkertaisen helminauhan. Soto kumarsi kohteliaasti, niinkuin hovimiehen sopi, ja tekeytyi ystäväksi. Mutta saatuaan selville, ettei siellä ollutkaan kultaa, hän päätti edes helmet ryöstää; hän otti kuningattaren vangiksi, antoi kaivaa päälliköitten haudoista kaikki vainajien mukaan pannut helmet, anastipa kuningattaren omankin kalliin helmilippaan, joka oli koko heimon aarre. Kuningatar kuitenkin pääsi karkaamaan ja sai vielä helmilippaansakin mukanaan viedyksi.
Kun oli tultu jo'ille, jotka virtasivat Atlantin merta kohti, niin käännyttiin länttä kohti, alituiseen taistellen intianeja vastaan. Mitä intianeja vangiksi saatiin, ne osaksi surmattiin, osaksi otettiin orjiksi; orjiksi otettujen täytyi seurata mukana, kahleet kaulassa, retkikunnan tavaroita kantaen ja leiripaikoilla viljaa jauhaen.
Osasta tavattiin hyvinkin viljeltyjä seutuja, vaikkei missään semmoisia rikkaita sivistysmaita, kuin Corteksen ja Pizarron vallottamat. Eräs päällikkö, Tascaluco nimeltään, rupesi retkikunnan oppaaksi, kun sai Sotolta hevosen; hän oli kooltaan semmoinen jättiläinen, että kun hän istui hevosensa selässä, niin jalat laahasivat maata. Mutta Tascaluco opastikin vieraansa vahvan intianilinnan luo, sillä hän aikoi heidät tuhota. Linnassa oli 80 suurta rakennusta, joissa kussakin sanottiin olevan 1000 miestä. Espanjalaiset kuitenkin viime hetkessä huomasivat vaaran, kävivät linnan kimppuun, hakkasivat kirveillä rikki puuportit ja sytyttivät majat tuleen. Soto itse haavottui taistelussa, mutta johti sitä kuitenkin loppuun saakka. Intianien naisetkin ottivat osaa tappeluun. Mutta kun tuli leviämistään levisi, niin täytyi intianien pyrkiä pakoon, varustuksiensa yli hypäten. Taistelua kesti yhdeksän tuntia. Espanjalaiset menettivät 83 miestä, mutta intianien mieshukan he arvostelivat 11,000 mieheksi. Kaduilla laskettiin päälle 3000 ruumista ja 4000 sai arvion mukaan tulipalossa surmansa, petollinen päällikkö ehkä näiden mukana.
Espanjalaiset masentuivat tästä vihamielisyydestä, jota vastaan oli sitä toivottomampi taistella, kun ei kultaa ollut missään. Suurin osa olisi mieluummin palannut kotia, mutta Soto päätti jatkaa retkeä, vaikka täytyikin ainiaan tapella ja varoa väjytyksiä. Eräässä suuremmassa keskustassa päätettiin taas viettää talvea. Syksyllä myöhään intianit eräänä yönä yllättivät retkikunnan ja sytyttivät majat ruokokattoineen palamaan. Tappelussa kaatui jälleen 40 espanjalaista ja sitä paitsi menetettiin puolensataa hevosta. Keväämmällä jatkettiin retkeä, milloin lounaita, milloin länttä kohti. Luultavasti oli Soto silloin Tennessee joen rannoilla ja saapui sitä pitkin Mississipille. Kun nimet ovat toiset kuin nykyiset, niin on vaikea saada matkasuunnista tarkkaa selkoa. Retkikunta oli jo menettänyt puolet miesluvustaan. Liitossa erään intianipäällikön kanssa Soto sitten teki sotaretken Mississippi joelle toista päällikköä vastaan, jonka pääkaupunki vallotettiin ja hävitettiin. Näissä tappeluissa ensi kerran nähtiin intianien riistävän kaatuneilta vihollisiltaan päänahkan. Soto meni Mississipin poikki ja löysi sen toisellakin puolelta hedelmällisiä viljeltyjä maita. Mutta siellä hän sairastui kuumeeseen ja kuoli keväällä 1541, 42:n vuoden ikäisenä, suureksi suruksi väelleen, joka oli häneen kovin kiintynyt. Ritari upotettiin yöllä erääseen Mississipin putaaseen, jotteivät intianit saaneet tietoa hänen kuolemastaan. Soton viimeisen toivomuksen mukaan sai Luis de Alvarado johdon.
Heinäkuun alussa retkikunta lähti Mississipiltä samoamaan länttä kohti, joutuen siten laajalle arolle ja sitten tuiki autioon erämaahan, jossa intianioppaatkin eksyivät. Kun ruokavarat loppuivat ja miehet alkoivat uupua, niin täytyi kääntyä takaisin Mississipille, vaikka edessäpäin oli näkynyt suuria vuoria, joissa ehkä olisi vihdoinkin ollut etsittyjä aarteita. Arvatenkin oli retkikunta siis kulkenut Kalliovuoriston itäiselle eteismaalle saakka. Paluumatkalla nääntyi paljon sotamiehiä puutteeseen, talvi tuli, ruoka oli hankittava ainaisilla taisteluilla. Mississipin rantarämeillä täytyi retkeläisten usein viettää yönsä ratsumiehet satulassa, jalkamiehet polviaan myöten suossa, sillä ei aina tavattu edes kuivaa maata leirin paikaksi. Paljain jaloin, eläinten vuotia vaatteinaan — oikeat vaatteet olivat jo aikoja sitten repaleina — saapuivat suuren retkikunnan tähteet marraskuun lopulla takaisin Mississipille lähelle sitä paikkaa, jossa kesällä oli sen poikki kuljettu. Siellä vallotettiin vesikaivannoilla suojeltu kylä ja asetuttiin siihen talvea viettämään. Retkikunnasta oli vielä jäljellä 320 miestä ja 70 hevosta. Mutta rasituksien jälkiseurauksista kuoli vielä talvenkin kuluessa monta miestä. Eräältä läheiseltä ystävälliseltä intianipäälliköltä saatiin ruokavaroja ja tultiin siten toimeen kevääseen saakka, jolloin päätettiin kulkea pitkin jokea merelle ja sitten pyrkiä takaisin espanjalaisiin siirtokuntiin. Maaliskuun ja huhtikuun kuluessa rakennettiin vankkoja, keulasta ja perästä kannellisia veneitä. Mutta Mississipin valtava kevättulva viivytti vielä monta viikkoa lähtöä. Joki alkoi nousta maaliskuun 10 p. ja täytti huhtikuun puolivälissä koko laajan laaksonsa, niin että vielä toukokuun puolivälissä Espanjalaisten asuman kylän kujat olivat tulvaveden vallassa ja vasta juhannuksen aikana oli saatu kokoon sen verran ruokatavaroita, että voitiin joelle lähteä. Tämä tapahtui kesäkuun viimeisinä päivinä. Kussakin veneessä oli noin viisikymmentä Espanjalaista ja neljä intiania, jotka lähtivät oppaiksi. Mutta joen suupuolen heimot olivat saaneet tiedon muukalaisten lähtöpuuhista. He sulkivat tien tuhannella sotikanootilla, joista toisissa oli viisikinkolmatta melojaa kummallakin puolella. Sotilaat olivat täydessä sotamaalissa, enimmäkseen mustan ja sinisen kirjavat, ja kanootit oli maalattu samoilla väreillä. Espanjalaisten täytyi veneineen raivata tiensä tämän suunnattoman veneliudan keskitse, takaa-ajoa ja taistelua kesti kymmenen päivää, ja moni heitti jälleen henkensä. Vasta sitten voitiin rauhassa matkata edelleen. Joki levisi niin leveäksi, että keskeltä tuskin näkyi alavia rantoja. Jokimatkan yhdeksäntenätoista päivänä saavuttiin merelle ja jatkettiin matkaa länteen päin rantoja pitkin. Kokonaisen päivän oli merivesi suistamon ulkopuolella Mississipin suolatonta vettä. Lähes kaksi kuukautta purjehdittiin sitten rantaa pitkin Mexicoa kohti, saatiin ruokavarain apua kalastuksella, joka oli hyvinkin satoisaa, ja poikettiin silloin tällöin maihin vettä ottamaan. Meriretki rantaa pitkin sujui odottamattoman hyvin, mutta lopulta yllättivät myrskyt ja rankkasateet, jotka monta kertaa uhkasivat täyttää ja upottaa veneet. Nukkumatta, syömättä seikkailijain täytyi ponnistella yhtä mittaa toista vuorokautta, ennenkuin pääsivät semmoiseen paikkaan, jossa saattoivat taas laskea maihin. Siinä toivossa, ettei Uuden Espanjan alue enää voinut olla kaukana, lähdettiin sitten maisin etelää kohti samoamaan. Mutta 70—80 kilometriä astuttuaan joukko oli niin uuvuksissaan, ettei se jaksanut kauemmaksi kulkea. Kaksi reippainta vain lähti edelleen tiedustelulle, kulkien yöllä, paljain jaloin, vain miekka ja kilpi aseinaan. Onneksi he piankin tapasivat intianin, jolta kuulivat Panuco nimisen siirtokunnan, joka oli määrätty Uuden Espanjan pohjoisrajaksi, jo olevan lähellä. Panucon espanjalainen maaherra otti ystävällisesti vastaan puolialastomat, eläinten vuotiin puetut maanmiehensä, jotka olivat enemmän villien kuin sivistyneitten ihmisten näköisiä, ja lähetti heidän tulostaan tiedon Mexicon varakuninkaalle Mendozalle. Tämä paikalla toimitti heille kaikenlaisia tarpeita, vaatteita, rohtoja ja ruokatavaroita.