The film Cabeza de Vaca is based on the 1542 historical account La Relacion (later reprinted in a 1749 edition titled Naufragios) by Alvar Nunez Cabeza de Vaca. Nicolas Echevarria and Guillermo Sheridan based their screenplay of Cabeza de Vaca on Naufragios. Cabeza de Vaca, in La Relacion, offers a first-hand account of his eight-year (1528-1536) odyssey of misfortune and extreme hardship through Florida, the American Southwest, and Mexico. The account has been translated into English by Buckingham Smith (1851), Fanny Bandelier (1905), Cyclone Covey (1961), Frances Lopez-Morillas (1993), and Martin Favata and Jose Fernandez 's translation  titled The Account: Alvar Nunez Cabeza deVaca's Relacion (Houston: Arte Publico,1993).

Cabeza de Vaca's written account provides the historical background of the doomed Panfilo Narvaez expedition, which was commissioned to claim Florida for the Spanish crown. Cabeza de Vaca was the treasurer of the expedition. A series of misfortunes including the loss of the fleet, a hurricane, a decision by Narvaez to split the remaining land and sea forces, and skirmishes with hostile natives resulted in the eventual complete disintegration and death of most members of the expedition. In 1528 the remaining survivors built crude rafts and set sail on the Gulf of Mexico hoping to reach a Spanish settlement in Cuba. Cabeza de Vaca and a group of survivors landed near what is now Galveston Island, Texas. For the next eight years Cabeza de Vaca wandered by foot across Texas, New Mexico, and the northern provinces of Mexico. During his sojourn in the American wilderness he was enslaved by natives but eventually became a trader and healer among an assortment of indigenous tribes. Cabeza de Vaca, Alonso Castillo, Andres Dorantes, and his Moor slave Estebanico were the only four survivors of the original expedition. They eventually reached a Spanish outpost in Culican, Mexico in 1536.

The film begins in a flash forward to the 1536 arrival of the survivors at the Mexican camp. The film flashes back to1528 when the expedition survivors are in the rafts in the Gulf of Mexico. Thus, the earlier historical aspects of the Narvaez expedition that Cabeza de Vaca relates in his book are not depicted. The rest of the film is based on the accounts of Cabeza de Vaca's transformation from native slave to shamanic healer. The movie, however, emphasizes mystical elements of Cabeza de Vaca's initiation into shamanism that are absent in the historical account. The historical Cabeza de Vaca evidences an interest in the general welfare of the indigenous tribes in his appeal to the Spanish crown in his narrative account. The film, however, takes a strong pro-native / anti-Spanish imperialism stance in its depiction of Cabeza de Vaca's spiritual bonding with natives and his enormous sorrow when he sees evidence of the enslavement of natives by the Spaniards. The film offers a representation of Cabeza de Vaca as a man who is profoundly transformed by his sojourn in the American wilderness from Spanish conquistador to a completely new "New World" identity forged by his mystical bonds with the native peoples.