En 1527, Pánfilo Narváez, el gobernador de Cuba, recibió órdenes reales de conquistar las tierras entre Río de las Palmas (hoy, Río Soto la Marina en Tamaulipas, México) y la península de la Florída (Krieger 21). Cabeza de Vaca, equipado con cartas de recomendación de la nobleza de Cadiz (debido a sus conexiones con el Duque de Medina Sigonia), fue entrevistado por Narváez para ser parte de su expedición (Suñe 118). Esta documentación fue suficiente y Cabeza de Vaca fue nombrado tesorero y aguacil mayor de la expedición el 15 de febrero de 1527 (Suñe 118). Es posible que Cabeza de Vaca se casó en esto años, pero no hay récord de niños (Favata y Fernández 12).
La armada de Narváez incluyía aproximadamente 600 soldados, colonizadores, y marineros, como también 12 esposas y 5 monjes. Viajaron primero a Sanlúcar de Barrameda, España y desde allí, hacia el mar abierto el 27 de junio 1527 (Krieger 22). El viaje tranquilo hacia el Mundo Nuevo sólo fue interrumpido por una parada breve en las Islas Canarias (Suñe 118); la armada llegó a Santo Domingo (en la isla de Hispaniola) y allí se quedo por 45 días para obtener reservas y caballos. Durante este tiempo, 140 hombres abandonaron la armada, tentados “por los partidos y promesas que los de la tierra les hicieron” (Cabeza de Vaca). Luego la armada partió para Santiago, Cuba, donde se “[rehicieron] de gente, de armas y de caballos” (Cabeza de Vaca). Allí, un hombre llamado Vasco Porcallo le ofreció a Narváez unas provisiones que tenía en Trinidad, un pueblo ubicado 100 leguas del puerto de Santiago. Narváez aceptó, pero sólo mandó un navío a Trinidad, mientras que los otros se quedaron en el Cabo de Santa Cruz– a mitad del camino entre Santiago y Trinidad. El Capitán Pantoja estaba encargado del navío que iba hacia Trinidad y Cabeza de Vaca lo acompañó (Cabeza de Vaca).
Y como si no fuera suficiente el abandono previo, un huracán llegó al Caribe, destruyendo parte de la armada. Cabeza de Vaca describe la tormenta violenta (de la cual no pudieron encontrar refugio) en la siguiente manera: “A esta hora el agua y la tempestad comenzó a crecer tanto, que no menos tormenta había en el pueblo que en el mar, porque todas las casas e iglesias se cayeron, y era necesario que anduviésemos siete u ocho hombres abrazados unos con otros para podernos amparar que el viento no nos llevase; y andando entre los árboles, no menos temor teníamos de ellos que de las casas, porque como ellos también caían, no nos matasen debajo. En esta tempestad y peligro anduvimos toda la noche, sin hallar parte ni lugar donde media hora pudiésemos estar seguros”. Al día siguiente (lunes), Cabeza de Vaca y los otros hombres buscaron sus naves a las orillas del mar. Al no encontrar nada, empezaron a buscar en los montes, donde finalmente encontraron la barquilla de un navío en un arbol y los cuerpos de sus compañeros. De acuerdo con Cabeza de Vaca, 60 personas y 20 caballos murieron en los navíos. Sólo los 30 que habían desembarcado sobrevivieron (Cabeza de Vaca).
Narváez y los otros hombres, que también habían sobrevivido la tormenta, llegaron a Trinidad el 5 de noviembre en los 4 navíos que quedaban. Asustados por el huracán violento, los hombres le rogaron a Narváez que los dejara pasar el invierno en Cuba antes de viajar hacia Florida. Estuvo de acuerdo y los mandó a Xagua bajo el cargo de Cabeza de Vaca. Durante este tiempo, Narváez probablemente cruzó Cuba, colectando provisiones, tripulación, y navíos (Krieger 22). Llegó a Xagua el 20 de febrero 1528, con un navío nuevo y un piloto llamado Miruelo; otro navío, capitaneado por Álvaro de la Cerda, los esperaba en La Habana. El 22 de febrero, la expedición partió para Florida, con “cuatrocientos hombres y ochenta caballos en cuatro navíos y un bergantín” (Cabeza de Vaca).
No pasó mucho tiempo antes de que Mirulo “metió los navíos por los bajíos que dicen de Canarreo, de manera que otro día dimos en seco, y así estuvimos quince días, tocando muchas veces las quillas de los navíos en seco” hasta que una tormenta “metió tanta agua en los bajíos, que [pudieron] salir” (Cabeza de Vaca). Tormentas persiguieron la armada hasta Florida. Finalmente, vieron tierra martes el 12 de abril 1528. El Jueves Santo, echaron anclas en la bahía, y el Viernes Santo, tomaron posesión de la tierra en nombre de España (Cabeza de Vaca). En este momente, sólo 42 de los 80 caballos aún estaban vivos, y los que estaban vivos estaban tan débiles que eran inútiles (Cabeza de Vaca).
Desde allí, entraron por la tierra adentro. Después de encuentros hostiles con los nativos, los españoles decidieron regresar a la costa. Sólo quedaban 200 hombres (Suñe 118). Afferados a la esperanza, los hombres construyeron 5 barcas entre el 4 de agosto y el 20 de septiembre (Cabeza de Vaca). Los hombres embarcaron hacia el oeste a lo largo de la costa del Golfo de México, buscando Pánuco, México. Desembarcaron en la Isla de Galvestón (o al oeste de allí) el 5 y 6 de noviembre 1528. Aquí, escucharon a los nativos hablar de otros españoles, miembros de otra expedición desastrosa. Estos hombres eran: Alonzo del Castillo Maldonado, Andrés Dorantes de Carranza, y Estevanico (el esclavo africano, también conocido como “Esteban”) (Krieger 1).
Todos estos hombres vivieron entre los nativos durante muchos años. En la primavera de 1529, Castillo Maldonado, Dorantes de Carranza, Estevanico, y aproximadamente 12 hombres dejaron al enfermo Cabeza de Vaca (probablemente tenía malaria) en búsqueda de Pánuco de nuevo (Cabeza de Vaca). Por el resto de la primavera y el verano, Cabeza de Vaca migró con los indios Karankawa, ayudándoles a recoger comida, llevar acabo tareas serviles, y hasta funcionando como comerciante, haciendo intercambios entre tribus (Cabeza de Vaca). Cabeza de Vaca no era el único español que dejaron atrás– Alaniz y Lope de Oviedo también se habían quedado (aunque éste se habían quedado por gusto). Alaniz falleció poco después de que se habían ido los hombres y Cabeza de Vaca se tardó casi tres años para convencer a Oviedo a que debería escapar con él (Cabeza de Vaca). Durante estos años, Cabeza de Vaca se escapó y vivió solo en tierra salvaje (Cabeza de Vaca).
Finalmente, en el verano de 1532, Oviedo decidió viajar con Cabeza de Vaca a lo largo de la costa. Sorprendentemente, en la punta meridonial de la Bahía Matagorda (entre Galvestón y Corpus Christi, Texas), encontraron a Alonzo del Castillo Maldonado, Andrés Dorantes de Carranza, y Estevanico, quienes habían sido tomados prisioneros por los Quevenes. No queriendo arriesgarse a ser hecho prisionero como sus amigos, Oviedo se regresó (Cabeza de Vaca). Los hombres que quedaron finalmente escaparon en la primavera de 1535 y empesaron a cruzar el continente, yendo hacia el oeste.
En diciembre 1535, los hombres empezaron a escuchar cuentos y ver señales de cristianos (Cabeza de Vaca). A finales de enero, Cabeza de Vaca se encontró con unos españoles en una partida de esclavos, “que recibieron gran alteración” de verlo “tan extrañamente vestido y en compañía de indios” (Cabeza de Vaca). Poco después, Cabeza de Vaca y sus compañeros se encontraron en desacuerdo con sus paisanos: “Y después de esto pasamos muchas y grandes pendencias con ellos, porque nos querían hacer los indios que traíamos esclavos” (Cabeza de Vaca). Después de prevenir la esclavitud de sus compañeros indios, los cuatro hombres llegaron por fin a la Ciudad de México en julio 1539.