Завоевание имело поразительный успех. За пять лет с начала вторжения почти весь Иберийский полуостров оказался под контролем мусульманских армий. Однако из этого правила были существенные и, как оказалось, роковые исключения. На севере Испании, как и в некоторых районах Среднего Востока, территория, контролируемая мусульманами, ограничивалась горизонталью 1000 метров. Это означало, что в горных южных долинах Пиренеев и Пикос-де-Эуропа, располагавшихся западнее в направлении к Астурии, собирались группы беженцев и непокорных жителей, желавших отстоять свою независимость. Рассказывают, что в Пикос-де-Эуропа их движение возглавил не-кий Пелайо, возможно, высокородный готт из придворных Родериха. Арабские источники ничего не рассказывают нам об истории этого восстания, а вот для христианского королевства Астурия его история стала легендой об основании их государства. Как сообщается в хронике Альфонсо III, составленной, возможно, после 900 года, арабы уже готовились арестовать Пелайо, но друзья предупредили его, и он скрылся в горах. Ландшафт Пикос-де-Эуропа сильно изрезан, с крутыми стенами ущелий и скалистыми утесами. Из-за частых дождей горы эти необыкновенно зеленые, с хорошо орошаемыми полями и лесами, с быстрыми реками. Этот ландшафт ничем не походил на открытые равнины Месеты на юге, и как небо от земли отличался от пустынь Северной Африки и Египта. Горы эти никогда в действительности не принадлежали римской Испании, в них не было больших городов, в них не прокладывали римские дороги.
Пелайо, как рассказывает хроника, сумел скрыться, выйдя на берег быстрой реки и, переплыв ее на лошади: его враги не сумели последовать за ним. Он бежал в горы и основал свой лагерь в пещере. Эта пещера стала центром сопротивления всего народа Астурии. Арабское правительство пришло в ярость и выслало армию численностью 187 000 человек — совершенно фантастическое число — для подавления восстания. Ее возглавил арабский командующий, которого источник называет Алькама, и таинственный епископ, называемый Оппа, согласившийся сотрудничать с мусульманами. Мусульмане сошлись с Пелайо высоко в горах, в местности под названием Ковадонга. Епископ обратился к Пелайо и спросил, как думает он устоять перед арабами, если те недавно разгромили всю армию готов. Пелайо ответил кратким благочестивым поучением, гласившим, что «Христос — наша надежда, и в этих малых горах, которые ты видишь перед собой, будет восстановлено благоденствие Испании и войско народа готов».
Переговоры были прерваны, и мусульмане атаковали. Великое множество их погибло, а остальные бежали. Битва у Ковадонги, датируемая обычно 717 годом, превратилась в легендарный символ начала христианского сопротивления. Тщетная попытка мусульманской армии подавить восстание немедленно отозвалась для них потерей контроля над северными поселениями, такими как Гихон, и основанием маленького независимого христианского королевства. Это королевство и подобные ему образования в долинах Пиренеев и Стране басков стали впоследствии основой христианской реконкисты.
В раннем мусульманском мире были и другие княжества, более или менее мирно сосуществовавшие с мусульманскими властями — например, в горах на севере Ирана христианские княжества горной Армении во многом напоминали христианскую северную Испанию. Впрочем, все они нисколько не угрожали власти мусульман над южными землями. Когда в X веке горцы-дейламиты из северного Ирана завоевали большую часть Ирана и Ирака, это была война мусульман с мусульманами, и они скоро растворились среди многочисленного мусульманского населения завоеванных земель. Армяне сохраняли независимость, но никогда не стремились к завоеваниям вне традиционных границ своей родины. Независимые государства северной Испании отличались тем, что сохранили, пусть и в малой мере, высокую культуру латинского христианства. В то же время они сохраняли память о королевствах визиготов и идею, что полуостров некогда принадлежал им целиком и должен снова вернуться к ним. Кроме того, у них была связь с большим христианским миром на севере. Эти обстоятельства означали, что в отличие от североиранских и армянских княжеств христиане Испании стали серьезной и постоянной угрозой контролю мусульман и наконец, по прошествии 800 лет, полностью вытеснили их с полуострова.