Папа Иннокентий III помог организовать грандиозный крестовый поход, направив соответствующую буллу французским и провансальским рыцарям. Он также позаботился о том, чтобы Альфонсо IX Леонский или кто-либо другой не заключили союза с мусульманами, дав право архиепископам Сантьяго и Толеро отлучать таких отступников. Однако Филипп II Август Французский, опасавшийся вторжения англичан, не решился отправиться на юг, и епископ Жоффруа Нантский был единственным магнатом севера, участвовавшим в походе. Зато из Южной Франции прибыли архиепископы Бордо и Нарбонны, а с ними многие пешие и конные крестоносцы из Анжу, Пуату, Бретани, Лиможа, Перигора, Сентонжа, Бордо, Ломбардии. Свое прибытие в Толедо крестоносцы ознаменовали еврейским погромом (чего арабы в испанских городах, кстати, не делали).
В июне 1212 г. в Толедо собралась величайшая христианская армия в истории Испании. Знать, включая не менее 16 грандов Кастилии и Арагона (в том числе Диего Лопес де Аро, сеньор Бискайи, и альферес Альваро Нуньес де Лара), многочисленные ополченцы городов, епископы Таррагоны, Барселоны, Толедо и еще 4 кастильских прелата со своими дружинами, тамплиеры и госпитальеры. Были здесь и южнофранцузские и прочие крестоносцы из-за Пиренеев. Войска короля Педро II Арагонского – 3000 каталоно-арагонских рыцарей и сильный отряд арбалетчиков – выступили на помощь кастильскому монарху из Льеиды в начале июня. Присоединился к армии Альфонсо и многочисленный отряд португальцев. Всего, по оценкам Родриго Хименеса, Кастилия, Арагон, Леон, Галисия, Португалия и Астурия выставили 10 000 кабальерос и 100 000 пехотинцев.
Король разместил войска в садах Толедо и снабдил необходимым денежным довольствием, лошадьми и различной амуницией. Для того чтобы обеспечить поход, Альфонсо напряг и свою казну, и тех, кто находился под его влиянием. Так, кампания 1212 г. стоила кастильскому духовенству половины его ежегодного дохода.
Перед походом король «дал рыцарское звание тем, кто его не имел, но был его достоин».
Стояла невыносимая жара, войска сходились медленно, приходилось ждать. Это раздражало иноземное воинство Христово, не привыкшее к столь знойному климату. Лишь 20 июня войско двинулось на юг в долину Гвадианы. Шли 3 колоннами – крестоносцы (ими командовал Диего Лопес), арагонцы и кастильцы. Через 2 дня армия халифа (андалузцы, берберы, арабы) тронулась из Севильи на Хаэн, горный район близ Баэсы, где и остановилась, поджидая развития событий. В 20-х числах июня реконкистадоры взяли замки Малагрон и Калатраву. Однако дележ добычи и жара раскололи христианское воинство. 29 июня архиепископ Бордо и многие другие рыцари сняли с себя обет и возвратились домой. На обратном пути они попытались ограбить Толедо, но горожане захлопнули перед ними ворота. Новости о беспорядках в лагере врага побудили халифа покинуть Хаэн и выступить на север в Баэсу.
Альфонсо двинулся дальше, в южную часть Ламанчи. Пали замки Аларкос, Каракуэль, Банавенте и Пьедрабуэна. К Корелю присоединился во главе 200 рыцарей Санчо VII Сильный, король Наварры, забывший о своей дружбе с мусульманами и ненависти к кастильцам. По пути король получил первые известия о том, что огромная мусульманская армия, численно превышающая его уменьшившиеся рати и возглавляемая лично халифом, сосредоточена в глубине Сьерра-Морены, разделявшей Кастилию и Андалусию, за единственным проходом туда – перевалом Мурадаль.
Подойдя 13 июля к перевалу, государь обнаружил, что тот в самой высокой и узкой части блокирован отрядами мусульман. Запасы продовольствия и воды иссякли, и на военном совете уже говорили о возвращении в Толедо, но некий пастух показал обходную дорогу. Затем проводник исчез неизвестно куда. По преданию, им был сам Св. Исидор – покровитель Мадрида. Альфонсо пересек Сьєрра-Морену и вошел в Андалусию, развернув свои войска на равнинах (по-испански «навас») Толоса, южнее горной гряды, в месте, именуемом Хисн аль-Икаб (по-испански Кастильо-де-ла-Квеста), в 64 км севернее Хаэна. Это была пересеченная местность, поросшая кустарником. Именно здесь разыгралась величайшая битва Реконкисты.