В Толедо последствия нетерпимости султана были другими. Тремя или четырьмя годами раньше, возвращаясь из поездки в Наварру, Евлогий провел несколько дней в этом городе, где его гостеприимно встретил благочестивый митрополит Вистремир. Есть все основания полагать, что Евлогий воспользовался благоприятной возможностью, чтобы возбудить ненависть жителей Толедо к арабскому правительству, для чего он обрисовал в весьма мрачных красках условия жизни христиан в Кордове. В любом случае жители Толедо высоко уважали Евлогия и живо интересовались мучениками в столице. Узнав, что Мухаммед начал преследования их собратьев по вере, они взяли в руки оружие, доверили командование некому Синдоле (возможно, это эквивалент вестготского Swintila или Chintila) и, опасаясь за судьбу заложников в Кордове, задержали своего арабского правителя, сообщив Мухаммеду, что, если он ценит жизнь своего человека, пусть вернет заложников в Толедо. Султан выполнил требование, и горожане освободили правителя. Но только война была уже объявлена, и так велик был страх, внушаемый толедцами, что гарнизон Калатравы покинул крепость, считая, что его безопасность не обеспечивается. Толедцы частично разрушили крепость, но вскоре после этого султан послал туда войска, и они выполнили восстановительные работы. Это было в 853 году. После этого он направил двух полководцев, чтобы возглавить наступление на Толедо, однако христиане прошли по теснинам Сьерра-Морены навстречу врагу, атаковали его в районе Андухара, обратили в бегство и разграбили лагерь.
Затем толедцы продвинулись к Андухару и стали угрожать столице. Мухаммед, понявший, что опасность можно устранить, только приняв срочные и энергичные меры, собрал все имевшиеся в его распоряжении войска и в июне 854 года повел их лично против Толедо. Со своей стороны Синдола, решив, что у него недостаточно сил, стал искать союзников. Он обратился к королю Леона Ордоньо I, который немедленно выслал на помощь большую армию под командованием Гатона, графа Бьерзо – согласно Ибн-Аззари, брата Ордоньо I. Ибн-Хальдун утверждает, что король Наварры тоже выделил некий контингент.
В городе теперь был очень сильный гарнизон, и Мухаммед, судя по всему, отказался от всех надежд его покорить. Но он сумел нанести большие потери врагу. Поместив главные силы своей армии в засаду за скалами, через которые течет Гваселете, он выступил против города во главе небольшого отряда и использовал артиллерию, чтобы разбить стены. Видя, что против них выступили слишком слабые силы, чтобы начать штурм, толедцы, удивленные дерзостью врага, потребовали, чтобы граф Гатон немедленно устроил боевую вылазку. Граф Гатон был только рад возможности отличиться. Во главе своих людей и толедцев он атаковал войска Мухаммеда, но те сразу же отступили, заманив противника в засаду. В разгар преследования войска Толедо и Леона неожиданно обнаружили себя в окружении массы противников. Никому не удалось спастись. «Сын Юлия (имя некого христианского лидера, Муса – имя ренегата), – писал придворный поэт, – крикнул Мусе, шедшему перед ним: «Гляди, я вижу смерть со всех сторон! Передо мной, за мной, подо мной!»… Скалы Гваселете скорбят по множеству рабов и необрезанных, оглашаясь многократно отражающимся эхом плачей».
Жестокие победители обезглавили восемь тысяч трупов и, сложив из голов курган, прыгали на нем, оглашая все вокруг криками радости. Впоследствии Мухаммед приказал прикрепить эти головы к стенам Кордовы и других городов и даже послал некоторые из них африканским принцам.
Удовлетворенный победой и уверенный, что толедцы, признавшие потерю двадцати тысяч человек, больше его не потревожат, Мухаммед вернулся в столицу, предусмотрев, чтобы в отношении толедцев постоянно тревожили правитель Калатравы и Талаверы и его сын Мунзир. Тем временем он продолжал притеснять христиан Кордовы. Он приказал разрушить монастырь Табанос, не без оснований считая его рассадником фанатизма. Он отдал на откуп налоги, выплачиваемые христианами, в результате чего сборы существенно увеличились. Тем не менее пыл фанатиков не ослаб, и, пока «мученики» продолжали добровольно идти на эшафот, Альваро и Евлогий яростно защищали их действия. Альваро с этой целью написал Indiculus luminosus, а Евлогий – Apologia Nartyrum. В Кордове такие апологии были необходимы, поскольку христиане города были терпеливы и покорны и приписывали свои страдания бессмысленному поведению фанатиков, а вовсе не нетерпимости султана. С другой стороны, в Толедо и окрестных городах христиане открыто симпатизировали фанатикам и Евлогию, и епископы провинции, собравшиеся для избрания митрополита после смерти Вистремира, единогласно выбрали Евлогия. Султан отказался позволить ему въехать в Толедо, но епископы упорствовали в своей решимости и, понимая, что рано или поздно вето будет снято, запретили выборы другого митрополита, пока жив Евлогий.