A la fin du IXe siècle, Mohamed de Cordoue, successeur d'Abderraman II, avec sa puissante armée, avait déjà franchi l'Ebre et parcouru la campagne de Navarre, emmenant captifs à Cordoue les enfants du roi de Navarre. Fortun Garces (882-905) passera ainsi vingt ans de sa vie à Cordoue avec sa sœur. Mais ce fut Sancho Garces (905-925) qui forgea le royaume de Navarre en s'opposant aux Musulmans. Il arriva à reconquérir les terres riches occupées par les maures et leurs alliés les Banu Qasi, des nobles wisigoths que les envahisseurs maures avaient converti à l’islam, fixant ainsi la frontière de la Navarre sur l'Ebre.
Or, les relations entre les populations chrétiennes soumises et leurs conquérants musulmans étaient difficiles, particulièrement en Alava et en Navarre. D’après l’universitaire Yvette Cardaillac-Hermosilla de l’Université de Bordeaux III, les prescriptions du Coran commandent à l’Islam de procéder à « une division en trois groupes : les Musulmans, les gens du Livre et les idolâtres ». Si les idolâtres sont exclus de toute « tolérance pluraliste », en revanche les gens du Livre (Chrétiens et Juifs) « bénéficient » de la Dhimma, véritable contrat de « protection-soumission » : ils sont admis avec leurs croyances et leur culte mais « devront être humiliés et payer leur admission dans la communauté des croyants » au moyen d’un impôt ou « Jizya ». La politique des califats espagnols islamiques au Moyen-âge oscillait entre l’extermination des chrétiens, leur conversion à l’Islam ou la collecte de l’impôt auprès des « Dhimmis » (soumis).
Cependant, l’éclatement au XIe siècle du califat omeyyade en une multitude de petits États ou « taifas » va pourtant accélérer la reconquête par les États chrétiens du Nord. En 1086, l’année qui suit la prise de Tolède, les dirigeants musulmans des taifas appellent à l’aide les Berbères almoravides, récents fondateurs d’un empire en Afrique du Nord qui  écrasent l’armée chrétienne à Sagrajas (1086) avant de rembarquer pour le Maroc. Les chrétiens n’en continuent pas moins la libération progressive des terres envahies par l’Islam alors que les Almohades qui ont remplacé la puissance almoravide en Afrique du Nord constituent leur nouvel ennemi. Malgré le désastre d’Alarcos en 1195, qui entraîne un traumatisme en Occident car, survenant peu après la reprise de Jérusalem par les musulmans, les chrétiens arrivent à se maintenir jusqu’au Tage. Désireux de poursuivre son expansion contre les États chrétiens – castillan et navarrais - du Nord de la péninsule, le nouveau calife almohade, Muhammad an-Nasîr (appelé « Miramamolin » par les chrétiens, par déformation du titre « al-Amîr al-Mu’Minin » signifiant émir des croyants) décida de lancer une grande offensive qui provoqua un effroi certain, jusqu’en terre d’Oc, du fait de la puissance militaire des almohades, alors à son sommet.
Une bataille décisive
Au milieu de l’année de l’année 1210, An-Nâsir proclame le djihad, traverse le détroit de Gibraltar avec une grande armée et prend la forteresse de Salvatierra, malgré sa défense désespérée. Alphonse VIII de Castille réclame l’aide des souverains voisins, du roi de France et du pape Innocent III qui déclare la croisade. Les prières pour la victoire et les troubadours diffusent la cause de la reconquête, engageant à s’enrôler afin de combattre les Almohades.
Fin mai 1212, les chrétiens se regroupent à Tolède. Les sources donnent des milliers de fantassins et de cavaliers chrétiens, parmi lesquels, les Navarrais accourus avec leur roi Sanche VII eurent un rôle décisif au côté des chevaliers venus d’Aragon, de Castille, du Léon et même du Portugal. Pour sa part, l’armée musulmane, sans doute supérieure en nombre, mais composée de Berbères, d’Arabes, de Turcs et de Noirs enrôlés souvent de force, se concentre à Séville. Les chrétiens avancent vers l’armée musulmane qui adopte une stratégie défensive. Le 14 juillet, les croisés établissent leur camp sur un haut plateau du versant sud de la sierra, dans l’actuelle province de Jaen, à 15 km au sud des limites de la région de Castilla-La Mancha. An-Nâsir, qui ne les attendait pas là, compte engager immédiatement les combats afin de déloger les chrétiens d’une position qui lui semblait défavorable.
La bataille de Las Navas de Tolosa va commencer.
Le lundi 16 juillet 1212, l’armée chrétienne se range en ordre de bataille. « Jamais tant et telles armes de fer n’avaient été vues en Espagne » rapporte la Chronique latine des rois de Castille. Les chrétiens sont 10.000 à 14.000. Les Castillans d’Alphonse VIII sont placés au centre, les Navarrais de Sanche VII à droite, avec les Catalans et les Aragonais à droite, les autres croisés se sont placés dans les rangs castillans. Face à eux, An-Nâsir aligne 20.000 à 25.000 hommes. Dans l’avant-garde et sur les flancs, des cavaliers turcs, berbères et arabes ; derrière la foule des volontaires pauvrement armée ; au centre et à l’arrière Almohades et Andalous avec une cavalerie lourde.
Les avant-gardes chrétiennes attaquent les cavaliers musulmans qui ripostent par une volte-face rapide qui placent les croisés au centre de l’armée almohade. L’arrivée des deuxièmes corps chrétiens empêche tout encerclement de la part des musulmans. An-Nâsir fait alors donner son arrière-garde contre les croisés, exténués, qui supportent mal ce nouvel assaut. Les pertes sont nombreuses chez les chrétiens et Alphonse VIII, un moment découragé, songeait même à abandonner le champ de bataille pour se reporter vers Salvatierra en essayant de venger son échec précédent. Voyant le moment décisif arriver, Sanche VII et ses Navarrais chargent et entraînent les troupes chrétiennes encore intactes. Les rangs musulmans s’effondrent. C’est une débandade. Les chevaliers avancent vers le calife qui abandonne le camp et fuit à Séville. Cette victoire de Las Navas de Tolosa sera due, en grande partie, au roi de Navarre Sancho VII « le Fort » : ce géant dont la taille (2m25) s’accompagnait d'une force herculéenne au service d'un courage indomptable avait dû « terroriser » les défenseurs de la tente de l'émir, protégée par une puissante palissade munie de vigoureuses chaînes et dont l'armature principale était constituée de chameaux et d'une élite de combattants noirs. Les Navarrais parvinrent à ouvrir une brèche dans ce système défensif et ramenèrent du combat les chaînes entourant la tente de Muhammad al Nasir qui s’enfuit à Séville. Selon la tradition établie par les chroniqueurs médiévaux, Sanche le Fort rapporta ces chaînes en Navarre comme trophée de victoire : elles remplaceront sur le blason navarrais l'antique aigle noir et figureront sur ceux de Saint-Jean-Pied-de-Port, Saint-Palais, Pampelune et bien d'autres localités du Pays Basque. Et, dans la vallée de Baztan, beaucoup de belles demeures typiquement navarraises seront ornées d’un blason à damier dont l’échiquier rappelle la partie de dames interrompue afin d’aller combattre victorieusement l’envahisseur maure à La Navas de Tolosa…
La tradition rapporte encore que Sanche VII le Fort fit construire l’église de Saint-Jean-Pied-de-Port en guise d’ex-voto à sa victoire. La ville se développe à cette époque : elle reçoit un for ou fuero, c'est-à-dire une charte de franchise fixant les droits et devoirs, et privilèges des habitants afin de favoriser entre autres l’implantation d’artisans (exemptions d’impôts, des terres pour construire leurs habitations et leurs boutiques). Au XIIIe siècle, à la mort de Sanche le Fort, c’est une ville commerciale prospère.
Mais le souverain navarrais ne sembla pas réclamer à ses alliés castillans qu’il avait pourtant sauvés le retour des territoires indûment confisqués quelques années auparavant. L’Alava et surtout le Guipuzcoa – avec Saint-Sébastien et Fontarabie – dont la perte privait la Navarre d’un débouché sur l’Océan. A ce propos, l’historien Eugène Goyheneche avait confié un jour à Michel Duvert sa vision très personnelle de cet épisode historique : « La Castille grandit, de même que l’Aragon, ils avancent dans la péninsule et ferment la Navarre qui se voit privée des terres de reconquête. Elle est coincée, réduite à n’être plus que la Navarre. Les autres ont toute la péninsule pour eux ! Sanche VII le Fort collabore avec Alphonse VIII de Castille alors qu’il aurait pu le battre. Or, il l’a aidé ! Et ça se passait à las Navas de Tolosa, aux portes de l’Andalousie » !