Em 1503, Álvar Núñez Cabeza de Vaca tinha perto de 15 anos (ao que tudo indica, ele nasceu em 1488) quando tornou-se um dos caballeros de Jerez, a serviço do duque de Medina Sidonia, sendo remunerado por isso.

Ele passaria quase um quarto de século como soldado. Serviu a quatro duques (terceiro, quarto, quinto e sexto) e atuou durante uma fase complexa da história da Andaluzia, marcada pela reconquista do território ocupado pelos muçulmanos e pela expansão de Castela no norte da África, tanto durante o reinado de Fernando e Isabel, os chamados reis católicos, quanto sob seu herdeiro, Carlos V. Desde o século XV que os grandes senhores, como os duques de Medina Sidonia forneciam barcos para expedições destinadas não apenas ao comércio, como à ações militares preventivas ou expansionistas.

Em abril de 1506, Álvar Núñez perdeu o avô que inspirou sua vida militar: Pedro de Vera Mendoza, o conquistador da ilha de Gran Canária. Cinco anos mais tarde, já órfão, deixou a casa de sua tia Beatriz, que praticamente o adotara, para ir lutar na Itália. Participou de muitos combates e destacou-se pela bravura no dia 11 de abril de 1512, durante a batalha de Ravena, que custou a vida de milhares de espanhóis. Ele próprio saiu gravemente ferido. Como prêmio, foi nomeado alferes da cidade de Gaeta, próximo a Nápoles.

Em 1520, já de volta ao ducado de Medina Sidonia, Cabeza de Vaca lutou contra os rebeles do movimento comunero e ajudou a reconquistar o Alcázar de Sevilha. Sua última participação militar na Espanha deve ter sido em 1522, na batalha de Puente de la Reina, em Navarra, numa das primeiras guerras ocasionadas pela rivalidade entre Carlos I e Francisco I da França.

Cansado dos combates, resolveu tentar a sorte no Novo Mundo, na condição de tesoureiro da expedição de Pánfilo de Narváez. Durante os quase dez anos em que viveu na América do Norte, Cabeza de Vaca não participou de nenhum combate. Mas na província do Rio da Prata, ele entraria novamente em combate, agora contra os guaicurus que haviam recusado sua proposta de paz. Segundo seu secretário particular, Pero Hernández, autor dos Comentários, nessa ocasião o governador foi na vanguarda, “atropelando quem estava na frente; e como vieram os índios inimigos e viram os cavalos, que nunca haviam visto, foi tão grande o susto que levaram que todos que puderam fugiram para as montanhas e se embrenharam nelas”.