Después de la derrota de Alarcos, y arrepentido el Rey Don Alfonso VIII de su amancebamiento con una judía, y luego de haber hecho penitencia, quiso, ayudado por los Reyes de Aragón y de Navarra, tomar el desquite de su derrota y se dirigió de nuevo contra los moros. Atravesaba su ejército el puerto de la Losa, comúnmente llamado el puerto de Muradal, cuando se encontró al Rey moro Mahomat Miramamolín fuertemente atrincherado en dicho puerto. Pasar adelante era ir a una nueva derrota; retroceder era también difícil, y acampar en los lugares donde se hallaba el ejército, imposible, por falta de pastos y por las dificultades del avituallamiento de los soldados.

En esta situación crítica, dice la leyenda que se le apareció un ángel a don Alfonso VIII; pero los historiadores opinan que fue un hombre llamado Martín Alhaja, ganadero, el cual dijo al Rey que él conocía un camino por donde el ejército pudiera salir del atolladero en que se había metido.

El Rey, desconfiando de este hombre, comisionó al Conde Lope Díaz de Garo y a García Romea para que comprobaran la certeza de sus manifestaciones.

Fueron los dos caballeros guiados por Martín de Alhaja, que les dijo: “En la cumbre de ese monte hallarán la cabeza de una vaca devorada por los lobos, y desde ese sitio verán un camino por donde poder salir”. Los dos caballeros hallaron, en efecto, la cabeza de la vaca, y vieron un camino por donde, sin peligro de ser atacados por los moros, podía tomar nuevas posiciones el ejército cristiano.

Así lo hizo éste, y una vez situado más favorablemente, arremetió a los moros y obtuvo el 16 de Julio de 1212 la memorable victoria de las Navas de Tolosa.

Con la narración de ese suceso que precedió a la famosa batalla y que exponen diversos tratadistas, coincide casi exactamente la que hace Argote de Molina, que es el autor que reunió más autorizados pormenores y más detalladas noticias de todo el proceso de aquella victoria.

He aquí lo que dice Argote, en relación con la existencia del mencionado Martín Alhaja y con el eficaz servicio que prestó al ejército cristiano:

“Queriendo cada uno de los Reyes de Castilla, Aragón y Navarra los primeros encuentros contra los moros, fueron de acuerdo de dar el cargo de ordenar las batallas a un caballero ampurdanés llamado Dalmau de Crexel, caballero anciano y tenido sin contradicción alguna por extremado y práctico en actos de guerra y armas. Este ordenó que el Rey don Alonso de Castilla tuviese la vanguardia, pues era el principal de aquella jornada, y era suya la conquista de la tierra y reino de los moros contra quien se peleaba. Al Rey don Sancho De Navarra dio el cuerpo de la batalla con gentes del reino de Castilla. Al Rey don Pedro de Aragón ordenó que fuese en la retaguardia. Y así marcharon con su ejército hasta llegar al castillo de Castro Ferral, donde hallaron ocupado el paso por los moros, que por la aspereza del monte fragosísimo estaban tan fuertes, que al ejército de los cristianos era imposible pasar, sin ponerse a riesgo de ser perdido. Por la cual los Reyes quedaron tan confusos, que en ningún Consejo se determinaban. Pero como la voluntad de Dios era no desamparar los que peleaban por la honra de su nombre, y mostrarles cómo su ayuda es cierta en el mayor conflicto a los que en Él esperan, estando en este trabajo llegó a ellos un pastor de ganado (cuales son hoy los grandes pastores de tierra de Soria) preguntando a gran priesa por los Reyes; y como fuese llevado a su presencia, díjoles con gran determinación que no estuviesen en cuidado, que él los pasaría sin peligro por el camino donde repostaba su ganado, que era lugar de mucha hierba y de buenas aguas. Lo cual, como oyesen los Reyes, entendiendo que el pastor venía guiado por la voluntad del cielo, prometiendo de le hacer grandes mercedes, enviaron con él, para ser ciertos de lo que decía, a Diego López de Haro y a García Romea. Los cuales, subiendo por una cuesta de lo alto de la sierra, divisaron el llano que el pastor había referido. Y certificados los Reyes, partieron con todo el ejército, con grande gozo y alegría, y subieron por la cuesta que llamaban del Emperador, por haber pasado por ella el Emperador don Alfonso, y guiólos el pastor tan bien, que los puso de frente del real de los moros, sábado en la noche, donde plantaron sus tiendas y se alojaron a vista de los enemigos. Llamábase este pastor Martín Alhaja, el cual había dado por seña a Diego López de Haro y a García Romea que en aquel paso que les mostraría hallarían la calavera de una vaca que Martín Alhaja les había referido.”

En la carta que el Rey Don Alfonso VIII envió a Su Santidad Inocencio III, y que puede considerarse como el parte oficial de la batalla de las Navas de Tolosa, se alude también a dicho Martín Alhaja, aunque omitiendo su nombre, y se confirma la ayuda que prestó a los cristianos en los siguientes párrafos:

“Porque el Rey de los moros era vecino nuestro, no quisimos combatir a Salvatierra, sino procediendo contra la multitud de moros venimos a cierta montaña, a la cual no había pasada sino en ciertos lugares; y como nos venimos al pie de aquel monte de nuestra parte, los moros de la otra parte tomaron lo alto del monte, queriéndonos impedir el paso; pero nuestros soldados, subiendo varonilmente (porque hasta entonces, porque moros habían venido a aquel lugar) los retrayeron con socorro varonilmente, y cierto castillo fortalecido, que por impedir el paso el Rey de los moros había edificado, conquistaron,  que se llamaba Ferrad. El cual ocupado, el ejército del Señor seguramente pudo subir a lo alto, donde tuvo mucho trabajo por la falta de aguas y aspereza del lugar. Los moros, viendo que aquel paso no podían ocupar, ocuparon otro paso que restaba a la salida del monte, muy escabroso; y tal era, que mil hombres podían defender a todos cuantos hombres hay debajo del cielo, y junto aqueste paso, de la otra parte, estaba todo el ejército de los moros y fijadas ya sus tiendas. Y como nos, por la falta de agua, no pudiésemos estar allí, ni pasar, por la dificultad del paso, ciertos de los nuestros aconsejaron que otra vez bajásemos al pie del monte, y a dos o tres ductas buscásemos otro paso Nos empero atendiendo el peligro de la fe y deshonra de nuestra persona, no quisimos tomar este consejo, eligiendo antes en las dificultad del paso morir por la fe, que buscando paso más fácil, en alguna manera ir atrás en el negocio de la fe. Y  como ya hubiésemos afirmado nuestro propósito a juicio de cierto labrador que Dios envió de repente, en el dicho lugar hallamos otro paso harto fácil los magnates varones que en la batalla los primeros ímpetus habían de tener”.

Habrá el lector observado que en esas narraciones se dice unas veces que Martín Alhaja era pastor, otras que era ganadero y otras que era labrador; pero hay que suponer que era ganadero y labrador, a la manera que lo fueron en aquel tiempo muchos hidalgos de Soria, Segovia, Cuenca, Molina y otras partes; pues algunos autores dicen que venía del linaje de Cisneros, y que traía las armas de éstos, lo cual es testimonio de que no era de baja condición, sino hidalgo de casa y solar conocidos.

Don Alfonso VIII, en premio del gran servicio que había prestado a su ejército, concedió a Martín Alhaja las siguientes

En campo de oro, siete jaqueles rojos, o lo que es lo mismo, escudo jaquelado de oro y gules, de quince piezas: ocho de oro y siete de gules; bordura de azur, con seis cabezas de vaca, de plata.

Hay autores que afirman que los jaqueles de oro y gules ya los traía Martín Alhaja en sus armas  por el linaje de Cisneros, del cual procedía, como ya se ha dicho, y que lo que don Alfonso VIII lo concedió para premiar su servicio, fue únicamente la bordura con las seis cabezas de vaca, por lo que Martín fue llamado el de la Cabeza de Vaca, También hay autores que dicen que ese mote lo tomó  por apellido, conservándolo sus descendientes y que los del linaje Cabeza de Vaca proceden de él y traen sus mismas armas. Esto último, sin embargo, ofrece bastantes dudas.

Otros Alaja, traen: En campo de azur, una banda, de oro, engolada en dragantes de sinople y acompañada, en lo alto, de una estrella de oro y, en lo bajo, de una flor de lis, del mismo metal.